文档章节

7种常见的排序算法

Izecson
 Izecson
发布于 2016/02/16 14:43
字数 3446
阅读 9
收藏 0
点赞 1
评论 0
package test.arithmetic;
public class SortMethod {
    
    public static void printArray(int[] array) {  
        System.out.print("{");  
        for (int i = 0; i < array.length; i++) {  
            System.out.print(array[i]);  
            if (i < array.length - 1) {  
                System.out.print(", ");  
            }  
        }  
        System.out.println("}");  
    } 
    
 /**
  * 1.冒泡排序 
  * 优点:稳定,比较次数已知;
  * 缺点:慢,每次只能移动相邻两个数据,移动数据的次数多。 
  * 初始关键字 [49 38 65 97 76 13 27 49]
  * 第一趟排序后 [38 49 65 76 13 27 49] 97
  * 第二趟排序后 [38 49 65 13 27 49] 76 97
  * 第三趟排序后 [38 49 13 27 49] 65 76 97 
  * 第四趟排序后 [38 13 27 49] 49 65 76 97 
  * 第五趟排序后 [38 13 27] 49 49 65 76 97 
  * 第六趟排序后 [13 27]38 49 49 65 76 97 
  * 第七趟排序后 [13] 27 38 49 49 65 76 97 
  * 最后排序结果 13 27 38 49 49 76 76 97
  */
 public static void bubbleSort() {
  int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
  for (int i = a.length - 1; i >= 0; i--) {
   for (int j = 0; j < i; j++) {
    if (a[j] > a[j + 1]) {
     int k = a[j];
     a[j] = a[j + 1];
     a[j + 1] = k;
    }
   }
  }
  for (int i = 0; i < a.length; i++) {
   System.out.print(a[i] + ", ");
  }
 }
 /**
  * 2.选择排序
  * ①初始状态:无序区为R[1..n],有序区为空。
  * ②第1趟排序
  * 在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  * ……
  * ③第i趟排序
  * 第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
  * 优点:稳定,比较次数与冒泡排序一样;
  * 缺点:相对之下还是慢。
  * 初始关键字 [49 38 65 97 76 13 27 49]
  * 第一趟排序后 13 [38 65 97 76 49 27 49]
  * 第二趟排序后 13 27 [65 97 76 49 38 49]
  * 第三趟排序后 13 27 38 [97 76 49 65 49]
  * 第四趟排序后 13 27 38 49 [49 97 65 76]
  * 第五趟排序后 13 27 38 49 49 [97 76 76]
  * 第六趟排序后 13 27 38 49 49 76 [76 97]
  * 第七趟排序后 13 27 38 49 49 76 76 [ 97]
  * 最后排序结果 13 27 38 49 49 76 76 97
 */
 public static void selectionSort() {
  int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
  int k = 0;
  for (int i = 0; i < a.length - 1; i++) {
   k = i;
   for(int j=i+1; j<a.length; j++){
    if(a[k] > a[j]){
     k = j;
    }
   }
   if(k != i){
    int temp = a[k];
    a[k] = a[i];
    a[i] = temp;
   }
   System.out.println("\n" + (i + 1) + ": ");
   for (int m = 0; m < a.length; m++) {
    System.out.print(a[m] + ", ");
   }
  }
 }
 
 /**
  * 3.插入排序
  * 已知一组,一组无序数据b[1]、b[2]、……b[m],需将其变成一个升序数列。先创建一个变量a。首先将不b[1]与b[2],如果b[1]大于b[2]则交换位置,否则不变;
  * 再比较b[2]与b[3], 如果b[3]小于b[2],则将b[3]赋值给a,再将a与b[1]比较,如果a小于b[1];则将b[2],b[1]依次后移;在将a放在b[1]处以此类推,直到排序结束。
  * 初始关键字 [49 38 65 97 76 13 27 59]
  * a b[1] b[2]? b[3]? b[4] b[5]? b[6]? b[7] b[8]
  * 1—–49? 49 >? 38 65 97 ? 76? 13 ? 27 59
  * 38 49 49 ……….
  * 38 38 49 ……….
  * 2—–38? 38 ? 49 < 65? 97 ? 76 13 27 59
  * 3—–38? 38 ? 49? 65 <97 ? 76 13 27 59
  * 4—-38? 38 49? 65 97> 76 13 27 59
  * 76 38 49 65 97 97……..
  * 76 38 49 65 76 97……..
 */
 public static void straightInsertionSort(){  
  int[] array = { 3, -1, 0, -8, 2, 1 };
     int sentinel , j;  
     for (int i = 1; i < array.length; i++) {  
         j = i - 1;  
         sentinel = array[i];//哨兵位  
         while (j >= 0 && sentinel < array[j]) {  
             array[j+1] = array[j];//将大于sentinel的值整体后移一个单位   
             j--;  
         }  
         array[j+1] = sentinel;  
     }  
     printArray(array);
 } 
 
 /**
  * 4.缩小增量排序(希尔排序)
  * 由希尔在1959年提出,又称希尔排序。
  * 已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。
  * 首先取一增量d(d<n),将a[1]、a[1+d]、a[1+2d]……列为第一组,a[2]、a[2+d]、a[2+2d]……列为第二组……,a[d]、a[2d]、a[3d]……列为最后一组以次类推,
  * 在各组内用插入排序,然后取d’<d,重复上述操作,直到d=1。增量d(1, 3, 7,15, 31, …, 2^k-1)是使用最广泛的增量序列之一.
  * 优点:快,数据移动少;
  * 缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。
  * 初始:d=5
  * 49 38 65? 97 76 13? 27 49 55? 44
  * 一趟结果
  * 13 27 49 55 44 49? 38 65 97 76
  * d=3 |———————-|———————-|———————|
  * 二趟结果
  * 13 44 49 38 27 49? 55 65 97? 76
  * d=1
  * 三趟结果
  * 13 27 38 44 49? 49 55 65 76? 97
  * 希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值 
  * 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强 
  * 版的插入排序 
  * 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列 
  * 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较 
  * 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4 
  * 第一次后increment的值变为3/2=1,此时对数组进行插入排序, 
  */
 public static void shellSort(){
  int j = 0;
  int temp = 0;
  int[] data = new int[] { 5, 2, 8, 9, 1, 3, 4 };
  for (int increment = data.length / 2; increment > 0; increment /= 2) {
   for (int i = increment; i < data.length; i++) {
    temp = data[i];
    for (j = i; j >= increment; j -= increment) {
     if (temp > data[j - increment]) {
      data[j] = data[j - increment];
     } else {
      break;
     }
    }
    data[j] = temp;
   }
  }
 }
 /**
  * 5.快速排序
  * 快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。
  * 已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。
  * 首先任取数据a[x]作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数据>a[x],
  * 然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]
  * 两组数据进行快速排序。
  * 优点:极快,数据移动少;
  * 缺点:不稳定。
  * 分段插入排序
  * @param args
  */
 public static void quicksort(int n[], int left, int right) {
  int dp;
  if (left < right) {
   dp = partition(n, left, right);
   quicksort(n, left, dp - 1);
   quicksort(n, dp + 1, right);
  }
 }
 public static int partition(int[] n, int left, int right) {
  int pivotkey = n[left];
  // 枢轴选定后永远不变,最终在中间,前小后大
  while (left < right) {
   while (left < right && n[right] >= pivotkey)
    --right;
   // 将比枢轴小的元素移到低端,此时right位相当于空,等待低位比pivotkey大的数补上
   n[left] = n[right];
   while (left < right && n[left] <= pivotkey)
    ++left;
   // 将比枢轴大的元素移到高端,此时left位相当于空,等待高位比pivotkey小的数补上
   n[right] = n[left];
  }
  // 当left == right,完成一趟快速排序,此时left位相当于空,等待pivotkey补上
  n[left] = pivotkey;
  return left;
 }
 public static void quicksortMain(){
  int array[] = { 9, 5, 4, 8, 7, 3, 2, 10 };
  quicksort(array, 0, array.length-1);
  printArray(array);
 }
 
 
 /**
  * 6.归并排序算法
  * 合并排序(MERGESORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。
  * 它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个 N/2? 个长度为2或1的有序子序列,再两两合并,如此重复,值得得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。
  * 例如数组A有7个数据,分别是: 49 38 65 97 76 13? 27,那么采用归并排序算法的操作过程如图7所示:
  * 初始值 [49] [38]? [65] [97] [76]? [13] [27]
  * 第一次合并之后 [38 ? 49] ? [65 ? 97]? [13 76] [27]
  * 第二次合并之后 [38 ? 49 ? 65 ? 97]? [13 27 76]
  * 第三次合并之后 [13 ? 27 ? 38 ? 49 ? 65 ? 76 ? 97]
  * 合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。
  * 合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一规律,当有N个子序列时可以推断出合并的次数是X(2? >=N,符合此条件的最小那个X)。
  * 其时间复杂度为:O(nlogn).所需辅助存储空间为:O(n)
  */
 public static void merge(int a[], int low, int poi, int high) {
  int l1 = poi - low + 1;
  int l2 = high - poi;
  int[] array1 = new int[l1 + 1];
  int[] array2 = new int[l2 + 1];
  for (int i = 0; i < l1; i++) {
   array1[i] = a[low + i];
  }
  for (int i = 0; i < l2; i++) {
   array2[i] = a[poi + 1 + i];
  }
  // 将数组中的最后一个元素设置为最大值,这样就不必担心会有数据元素剩余,
  // 同时k的取值范围决定了无穷值不会被添加到原数据中
  array1[l1] = Integer.MAX_VALUE;
  array2[l2] = Integer.MAX_VALUE;
  int i = 0;
  int j = 0;
  for (int k = low; k <= high; k++) {
   if (array1[i] <= array2[j]) {
    a[low++] = array1[i];
    i++;
   } else {
    a[low++] = array2[j];
    j++;
   }
  }
 }
 
 public static void mergeSort(int a[], int low, int high) {
  if (low == high) {
   return;
  } else {
   int poi = (low + high) / 2;
   mergeSort(a, low, poi);
   mergeSort(a, poi + 1, high);
   merge(a, low, poi, high);
  }
 }
 
 public static void mergeSortTest() {
  int[] array = { 1, 3, 6, 4, 13, 14, 8, 12, 9, 7, 0};
  mergeSort(array, 0, array.length - 1);
  printArray(array);
 }
 
 
 /**
  * 7. 堆排序
  * 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
  * 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
  * n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
  * (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
  * 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
  * (1)用大根堆排序的基本思想
  * ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
  * ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
  * ③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
  * 直到无序区只有一个元素为止。
  * (2)大根堆排序算法的基本操作:
  * ① 初始化操作:将R[1..n]构造为初始堆;
  * ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
  * 注意:
  * ①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
  * ②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
  */
 public static void heapSort(int[] array) {
  buildHeap(array);// 构建堆
  int n = array.length;
  int i = 0;
  for (i = n - 1; i >= 1; i--) {
   swap(array, 0, i);
   heapify(array, 0, i);
  }
 }
 public static void buildHeap(int[] array) {
  int n = array.length;// 数组中元素的个数
  for (int i = n / 2 - 1; i >= 0; i--)
   heapify(array, i, n);
 }
 public static void heapify(int[] A, int idx, int max) {
  int left = 2 * idx + 1;// 左孩子的下标(如果存在的话)
  int right = 2 * idx + 2;// 左孩子的下标(如果存在的话)
  int largest = 0;// 寻找3个节点中最大值节点的下标
  if (left < max && A[left] > A[idx])
   largest = left;
  else
   largest = idx;
  if (right < max && A[right] > A[largest])
   largest = right;
  if (largest != idx) {
   swap(A, largest, idx);
   heapify(A, largest, max);
  }
 }
 public static void swap(int[] array, int i, int j) {
  int temp = 0;
  temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }
 //---------------------------------
 
 
 public static void main(String[] args) {
  int array[] = {11,2,3,14,5,6,1,8,9};
  heapSort(array);
  printArray(array);
 }
}

© 著作权归作者所有

共有 人打赏支持
Izecson

Izecson

粉丝 5
博文 59
码字总数 128528
作品 0
程序员
记录一下前段日子的面试问题

AOP如何工作, 实现原理. 2. 常见查找算法, 排序算法. 问我: 二分查找, 以及: 快速排序, 插入排序...问了我4~5种 3. MYSQL常见的类型. 以及区别在哪儿? 还有锁的概念 4. 事物, 以及实现原理....

陈袁at互联 ⋅ 2014/09/24 ⋅ 0

程序员必须知道的十大基础实用算法及其讲解

https://mp.weixin.qq.com/s/JZj5yWuykGGh3ORsmCn_gw 常见的七种排序算法解析 http://mp.weixin.qq.com/s/XD0T4zgLr58E3mPmGB_tpA...

素雷 ⋅ 2017/11/17 ⋅ 0

[译] 排序算法入门 — Go 语言实现

[译] 排序算法入门 — Go 语言实现 Go语言学习园地博客2017-07-0915 阅读 go算法排序 排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法,如果你...

Go语言学习园地博客 ⋅ 2017/07/09 ⋅ 0

编程面试过程中常见的10大算法

1. 字符串 如果IDE没有代码自动补全功能,所以你应该记住下面的这些方法。 toCharArray() // 获得字符串对应的char数组Arrays.sort() // 数组排序Arrays.toString(char[] a) // 数组转成字...

白志华 ⋅ 2015/09/19 ⋅ 0

排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien ⋅ 2016/06/17 ⋅ 0

八大排序算法-概要

常见的算法大概有8种,是我们需要掌握的。这些排序又可以分为排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,...

驛路梨花醉美 ⋅ 2016/06/20 ⋅ 0

快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题...

杨军军 ⋅ 2011/04/06 ⋅ 0

快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题...

阮一峰 ⋅ 2011/04/04 ⋅ 0

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影 ⋅ 2017/05/12 ⋅ 0

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影 ⋅ 2017/05/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JDK1.6和JDK1.7中,Collections.sort的区别,

背景 最近,项目正在集成测试阶段,项目在服务器上运行了一段时间,点击表格的列进行排序的时候,有的列排序正常,有的列在排序的时候,在后台会抛出如下异常,查询到不到数据,而且在另外一...

tsmyk0715 ⋅ 8分钟前 ⋅ 0

spring RESTful

spring RESTful官方文档:http://spring.io/guides/gs/rest-service/ 1. 可以这么去理解RESTful:其实就是web对外提供的一种基于URL、URI的资源供给服务。不是一个原理性知识点。是一个方法论...

BobwithB ⋅ 10分钟前 ⋅ 0

C++ 中命名空间的 5 个常见用法

相信小伙伴们对C++已经非常熟悉,但是对命名空间经常使用到的地方还不是很明白,这篇文章就针对命名空间这一块做了一个叙述。 命名空间在1995年被引入到 c++ 标准中,通常是这样定义的: 命名...

柳猫 ⋅ 12分钟前 ⋅ 0

@Conditional派生注解

@Conditional派生注解(Spring注解版原生的@Conditional作用) 作用:必须是@Conditional指定的条件成立,才给容器中添加组件,配置配里面的所有内容才生效; @Conditional扩展注解 作用(判...

小致dad ⋅ 13分钟前 ⋅ 0

适配器模式

适配器模式 对象适配器 通过私有属性来实现的类适配器 通过继承来实现的接口适配器 通过继承一个默认实现的类实现的

Cobbage ⋅ 17分钟前 ⋅ 0

Java 限流策略

概要 在大数据量高并发访问时,经常会出现服务或接口面对暴涨的请求而不可用的情况,甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流,当请求达到一定的并发数或速...

轨迹_ ⋅ 20分钟前 ⋅ 0

GridView和子View之间的间隙

默认的情况下GridView和子View之间会有一个间隙,原因是GridView为了在子View被选中时在子View周围显示一个框。去掉的办法如下: android:listSelector="#0000" 或 setSelector(new ColorDra...

国仔饼 ⋅ 24分钟前 ⋅ 0

idea插件开发

1 刷新页面要使用多线程 2 调试要使用restart bug 不要去关闭调试的idea 否则再次启动会卡住

林伟琨 ⋅ 24分钟前 ⋅ 0

Java 内存模型

物理机并发处理方案 绝大多数计算任务,并不是单纯依赖 cpu 的计算完成,不可避免需要与内存交互,获取数据。内存要拿到数据,需要和硬盘发生 I/O 操作。计算机存储设备与 cpu 之间的处理速度...

长安一梦 ⋅ 31分钟前 ⋅ 0

思路分析 如何通过反射 给 bean entity 对象 的List 集合属性赋值?

其实 这块 大家 去 看 springmvc 源码 肯定可以找到实现办法。 因为 spirngmvc 的方法 是可以 为 对象 参数里面的 list 属性赋值的。 我也没有看 具体的 mvc 源码实现,我这里只是 写一个 简...

之渊 ⋅ 51分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部