个人随笔
目录
Java实现九种排序算法
2019-11-08 23:52:23

一、插入排序

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

关键问题：在前面已经排好序的序列中找到合适的插入位置。

方法：直接插入排序、二分插入排序、希尔排序

1、直接插入排序

基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

java实现

  1. public class ZhiJieChaRu {
  2.     /**
  3.      * 直接插入排序第一版
  4.      * @param a
  5.      * @return
  6.      */
  7.     public static int[] sort1(int[] a) {
  8.         //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次 
  9.         //这里可以直接i=1从第二位开始处理也一样
  10.         for(int i=1;i<a.length;i++) {
  11.             //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
  12.             for(int j=i-1;j>=0;j--) {
  13.                 //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
  14.                 if(a[j+1]>a[j]) {
  15.                     break;
  16.                 }else {
  17.                         //这种每次比较后都马上移动，每次都定义临时变量，我们其实可以找到位置，最后再出入一次即可
  18.                         int temp = a[j+1];
  19.                         a[j+1]=a[j];
  20.                         a[j]=temp;
  21.                     }
  22.                 }
  23.             }
  24.             return a;
  25.     }
  27.     /**
  28.      * 插入排序改进版，找到位置最后才插入
  29.      * @param a
  30.      * @return
  31.      */
  32.     public static int[] sort2(int[] a) {
  33.         //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次 
  34.         //这里可以直接i=1从第二位开始处理也一样
  35.         for(int i=1;i<a.length;i++) {
  36.             //缓存待排序的记录
  37.             int temp = a[i];
  38.             int j;//这个是待插入的位置-1
  40.             //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
  41.             for(j=i-1;j>=0;j--) {
  42.                 //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
  43.                 if(temp>a[j]) {
  44.                     break;
  45.                 }else {
  46.                     //把当前记录往后面移动一位
  47.                     a[j+1]=a[j];
  48.                 }
  49.             }
  50.             a[j+1]=temp;
  51.         }
  52.             return a;
  53.     }
  54.     public static void main(String[] args) {
  55.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  56.         System.out.print("排序之前：");
  57.         for (int i = 0; i < a.length; i++) {
  58.             System.out.print(a[i]+" ");
  59.         }
  60.         System.out.println();
  61.         System.out.print("sort1：");
  62.         int[] a1 = sort1(a);
  63.         int[] a2 = sort2(a);
  64.         for (int i = 0; i < a1.length; i++) {
  65.             System.out.print(a1[i]+" ");
  66.         }
  67.         System.out.println();
  68.         System.out.print("sort2：");
  69.         for (int i = 0; i < a2.length; i++) {
  70.             System.out.print(a2[i]+" ");
  71.         }
  72.     }
  73. }

上面有两种实现方法，第二种sort2比较好，不用每次都新建temp;

分析
直接插入排序是稳定的排序。

文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n^2)，这时最坏的情况。

直接插入排序的平均时间复杂度为O(n^2)。

2、二分法插入排序

基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。

Java实现

  1. public class ErFenCharRu {
  3.     public static void main(String[] args) {
  4.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  5.         //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次 
  6.         //这里可以直接i=1从第二位开始处理也一样
  7.         for(int i=1;i<a.length;i++) {
  8.             //缓存待排序的记录
  9.             int temp = a[i];
  10.             //下面用二分法来在前面排好序的位置中找到插入的位置
  11.             //找到前面已排序的起点
  12.             int left = 0;
  13.             //找到已排序的终点
  14.             int right = i-1;
  16.             //中间位置坐标
  17.             int mid = 0;
  19.             //如果左边小于右边，就表明数据大于1，可以用二分法
  20.             while(left<=right) {
  21.                 //这个如果是偶数，比如4，则第二位当做中间值，若是5则第三位
  22.                 mid = (right+left)/2;
  23.                 //对比当前排序的数目和该数据的大小、
  24.                 if(temp>a[mid]) {
  25.                     //继续右边比较
  26.                     left = mid+1;
  27.                 }else {
  28.                     //继续左边比较
  29.                     right = mid-1;
  30.                 }
  31.             }
  32.             //循环结束后，left值和right值一定相同，并且比最一次比较的mid向左或者右偏移一位，所以位置就是left插入
  33.             //此时必须把已排序好的从left开始往后移动
  35.             //这里找到位置后，需要把该位置往后面的都右移
  36.             for (int j = i-1; j >= left; j--) {
  37.                 a[j+1] = a[j];
  38.             }
  39.             if(left != i){
  40.                 a[left] = temp;
  41.             }
  42.         }
  43.         for (int i = 0; i < a.length; i++) {
  44.             System.out.print(a[i]+" ");
  45.         }
  46.     }
  48. }

分析
当然，二分法插入排序也是稳定的。

　　二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n^2)。

3、希尔排序

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

java实现

  1. public class XiEr {
  3.     public static void main(String[] args) {
  4.         //希尔排序
  5.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  6.         for (int i = 0; i < a.length; i++) {
  7.             System.out.print(a[i]+" ");
  8.         }
  9.         //主要是取增量d
  10.         int d = a.length;
  11.         while(true) {
  12.             d=d/2;
  13.             //开始进行分组插入排序,对d组进行排序，到最后d=1 就是一组排序
  14.             for(int x=0;x<d;x++) {
  16.                 //每一组分别进行直接插入排序
  17.                 for(int i=x+d;i<a.length;i=i+d) {
  18.                     //缓存待排序的记录
  19.                     int temp = a[i];
  20.                     int j;//这个是待插入的位置-1
  22.                     //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
  23.                     for(j=i-d;j>=0;j=j-d) {
  24.                         //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
  25.                         if(temp>a[j]) {
  26.                             break;
  27.                         }else {
  28.                             //把当前记录往后面移动一位
  29.                             a[j+d]=a[j];
  30.                         }
  31.                     }
  32.                     a[j+d]=temp;
  33.                 }
  34.             }
  35.             //因为可能会只有一个元素
  36.             if(d == 1||d==0){
  37.                 break;
  38.             }
  39.         }
  40.           System.out.println();
  41.             for (int i = 0; i < a.length; i++) {
  42.                 System.out.print(a[i]+" ");
  43.             }
  45.     }
  47. }

分析
我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序的时间性能优于直接插入排序，原因如下：

（1）当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

（2）当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

（3）在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

　　因此，希尔排序在效率上较直接插人排序有较大的改进。

　　希尔排序的平均时间复杂度为O(nlogn)。

二、选择排序

思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。

关键问题：在剩余的待排序记录序列中找到最小关键码记录。

方法：简单选择排序、堆排序

1、简单选择排序

基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

java实现

  1. public class JianDanXuanZe {
  3.     public static void main(String[] args) {
  4.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  5.         //这里每一个数都要做比较
  6.         for (int i = 0; i < a.length; i++) {
  7.             //假设第一个数是最小的数
  8.             int min =a[i];
  9.             int n=i; //最小数的索引
  10.             //从后面找出最小的数，以及最小的数的位置
  11.             for(int j=i+1;j<a.length;j++) {
  12.                 if(a[j]<min) {
  13.                     //最小数的值
  14.                     min = a[j];
  15.                     //最小数的位置
  16.                     n=j;
  17.                 }
  18.             }
  19.             //把当前的值和最小数的位置那个值替换
  20.             a[n]=a[i];
  21.             a[i]=min;
  22.         }
  23.         for (int i = 0; i < a.length; i++) {
  24.             System.out.print(a[i]+" ");
  25.         }
  28.     }

分析

简单选择排序是不稳定的排序。

时间复杂度：T(n)=O(n2)。

2、堆排序

基本思想
堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义：具有n个元素的序列 （h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二 叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。

java实现

  1. public class HeapSort {
  2.     public static void main(String[] args) {
  3.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  4.         int arrayLength=a.length;  
  5.         //循环建堆  
  6.         for(int i=0;i<arrayLength-1;i++){  
  7.             //建堆  
  8.             buildMaxHeap(a,arrayLength-1-i);  
  9.             //交换堆顶和最后一个元素  
  10.             swap(a,0,arrayLength-1-i);  
  11.             System.out.println(Arrays.toString(a));  
  12.         }  
  13.     }
  14.     //对data数组从0到lastIndex建大顶堆
  15.     public static void buildMaxHeap(int[] data, int lastIndex){
  16.          //从lastIndex处节点（最后一个节点）的父节点开始 
  17.         for(int i=(lastIndex-1)/2;i>=0;i--){
  18.             //k保存正在判断的节点 
  19.             int k=i;
  20.             //如果当前k节点的子节点存在  
  21.             while(k*2+1<=lastIndex){
  22.                 //k节点的左子节点的索引 
  23.                 int biggerIndex=2*k+1;
  24.                 //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
  25.                 if(biggerIndex<lastIndex){  
  26.                     //若果右子节点的值较大  
  27.                     if(data[biggerIndex]<data[biggerIndex+1]){  
  28.                         //biggerIndex总是记录较大子节点的索引  
  29.                         biggerIndex++;  
  30.                     }  
  31.                 }  
  32.                 //如果k节点的值小于其较大的子节点的值  
  33.                 if(data[k]<data[biggerIndex]){  
  34.                     //交换他们  
  35.                     swap(data,k,biggerIndex);  
  36.                     //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值  
  37.                     k=biggerIndex;  
  38.                 }else{  
  39.                     break;  
  40.                 }  
  41.             }
  42.         }
  43.     }
  44.     //交换
  45.     private static void swap(int[] data, int i, int j) {  
  46.         int tmp=data[i];  
  47.         data[i]=data[j];  
  48.         data[j]=tmp;  
  49.     } 
  50. }

分析

　　堆排序也是一种不稳定的排序算法。

　　堆排序优于简单选择排序的原因：

　　直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

　　堆排序可通过树形结构保存部分比较结果，可减少比较次数。

　　堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

三、交换排序

1、冒泡排序

基本思想：让数组当中相邻的两个数进行比较，数组当中比较小的数值向下沉，数值比较大的向上浮！外层for循环控制循环次数，内层for循环控制相邻的两个元素进行比较。

java实现

  1. public class MaoPao {
  3.     public static void main(String[] args) {
  4.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  5.         //1、两两比较，如果前者比后者者大则交换位置
  6.         //2、每遍历一圈最大的数就会冒到最后，则确定了本轮比较中的最大值放到最后不动
  7.         //3、循环1、2直至遍历完所有
  8.         for (int i = 0; i < a.length-1; i++) {//外循环循环n-1次
  9.             for (int j = 1; j < a.length-i; j++) {//内循环每一次要比较n-i次
  10.                 if(a[j-1]>a[j]){
  11.                     int temp=a[j-1];
  12.                     a[j-1]=a[j];
  13.                     a[j]=temp;
  14.                 }
  15.             }
  16.         }
  17.         for (int i = 0; i < a.length; i++) {
  18.             System.out.print(" "+a[i]);
  19.         }
  20.     }
  22. }

注意，一定是两两交换而不是一个数与后面所有数交换

分析

冒泡排序是一种稳定的排序方法。　

若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)

若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)

冒泡排序平均时间复杂度为O(n2)

2、快速排序

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

java实现

  1. public class Quick {
  2.     public static  void quick(int[] a) {
  3.         if(a.length>0) {
  4.             quickSort(a,0,a.length-1);
  5.         }
  7.     }
  8.     private static void quickSort(int[] a, int low, int high) {
  9.         if(low<high) {
  10.             //选择基准元素
  11.              int middle = getMiddle(a,low,high);
  12.              quickSort(a, 0, middle-1);
  13.              quickSort(a, middle+1, high);
  14.         }
  16.     }
  17.     private static int getMiddle(int[] a, int low, int high) {
  18.         //假设第一个是基准元素
  19.         int temp = a[low];
  20.         while(low<high) {
  21.             //找到比基准元素小的位置
  22.             while(low<high&&a[high]>=temp) {
  23.                 high--;
  24.             }
  25.              a[low] = a[high];
  26.              //当队首元素小于等于tmp时,向前挪动low指针
  27.              while(low<high && a[low]<=temp){
  28.                    low++;
  29.              }
  30.              a[high] = a[low];
  31.         }
  32.         a[low] = temp;
  33.         return low;
  34.     }
  35.     public static void main(String[] args) {
  36.         int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
  37.         quick(a);
  38.         for (int i = 0; i < a.length; i++) {
  39.             System.out.print(a[i]+" ");
  40.         }
  41.     }
  43. }

分析

快速排序是不稳定的排序。

快速排序的时间复杂度为O(nlogn)。

当n较大时使用快排比较好，当序列基本有序时用快排反而不好。

四、归并排序

基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

原理
归并排序是一种递归算法，不断将列表拆分为一半，如果列表为空或有一个项，则按定义进行排序。如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。一旦对两半排序完成，获取两个较小的排序列表并将它们组合成单个排序的新列表的过程

归并细节：

比如有两个已经排序好的数组，如何将他归并成一个数组？

我们可以开辟一个临时数组来辅助我们的归并。也就是说他比我们插入排序也好，选择排序也好多使用了存储的空间，也就是说他需要o（n）的额外空间来完成这个排序。只不过现在计算机中时间的效率要比空间的效率重要的多。无论是内存也好还是硬盘也好可以存储的数据越来越多，所以设计一个算法，时间复杂度是要优先考虑的。

整体来讲我们要使用三个索引来在数组内进行追踪。

蓝色的箭头表示最终选择的位置，而红色的箭头表示两个数组当前要比较的元素，比如当前是2与1比较，1比2小，所以1放到蓝色的箭头中，蓝色的箭头后移，1的箭头后移。

然后2与4比较，2比4小那么2到蓝色的箭头中，蓝色箭头后移，2后移，继续比较…….

归并思路就是这样了，最后唯一需要注意的是那个先比较完的话，那么剩下的直接不需要比较，把后面的直接移上去就可以了，这个需要提前判定一下。

java实现

  1. public class GuiBin {
  2.     public static void main(String[] args) {
  3.         int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
  4.         System.out.println("排序之前：");
  5.         for (int i = 0; i < a.length; i++) {
  6.             System.out.print(a[i]+" ");
  7.         }
  8.         //归并排序
  9.         mergeSort(a,0,a.length-1);
  10.         System.out.println();
  11.         System.out.println("排序之后：");
  12.         for (int i = 0; i < a.length; i++) {
  13.             System.out.print(a[i]+" ");
  14.         }
  15.     }
  17.     private static void mergeSort(int[] a, int left, int right) {
  18.         if(left<right){
  19.             int middle = (left+right)/2;
  20.             //对左边进行递归
  21.             mergeSort(a, left, middle);
  22.             //对右边进行递归
  23.             mergeSort(a, middle+1, right);
  24.             //合并
  25.             merge(a,left,middle,right);
  26.         }
  27.     }
  29.     private static void merge(int[] a, int left, int middle, int right) {
  30.         int[] tmpArr = new int[a.length];
  31.         int mid = middle+1; //右边的起始位置
  32.         int tmp = left;
  33.         int third = left;
  34.         while(left<=middle && mid<=right){
  35.             //从两个数组中选取较小的数放入中间数组
  36.             if(a[left]<=a[mid]){
  37.                 tmpArr[third++] = a[left++];
  38.             }else{
  39.                 tmpArr[third++] = a[mid++];
  40.             }
  41.         }
  43.         //将剩余的部分放入中间数组
  44.         while(left<=middle){
  45.             tmpArr[third++] = a[left++];
  46.         }
  47.         while(mid<=right){
  48.             tmpArr[third++] = a[mid++];
  49.         }
  50.         //将中间数组复制回原数组
  51.         while(tmp<=right){
  52.             a[tmp] = tmpArr[tmp++];
  53.         }
  54.     }
  55. }

分析

归并排序是稳定的排序方法。

归并排序的时间复杂度为O(nlogn)。

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

五、基数排序

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

java实现

  1. public class JiShu {
  2.     public static void main(String[] args) {
  3.         int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
  4.         System.out.println("排序之前：");
  5.         for (int i = 0; i < a.length; i++) {
  6.             System.out.print(a[i]+" ");
  7.         }
  8.         //基数排序
  9.         sort(a);
  10.         System.out.println();
  11.         System.out.println("排序之后：");
  12.         for (int i = 0; i < a.length; i++) {
  13.             System.out.print(a[i]+" ");
  14.         }
  15.     }
  17.     private static void sort(int[] array) {
  18.         //找到最大数，确定要排序几趟
  19.         int max = 0;
  20.         for (int i = 0; i < array.length; i++) {
  21.             if(max<array[i]){
  22.                 max = array[i];
  23.             }
  24.         }
  25.         //判断位数
  26.         int times = 0;
  27.         while(max>0){
  28.             max = max/10;
  29.             times++;
  30.         }
  31.         //建立十个队列
  32.         List<ArrayList> queue = new ArrayList<ArrayList>();
  33.         for (int i = 0; i < 10; i++) {
  34.             ArrayList queue1 = new ArrayList();
  35.             queue.add(queue1);
  36.         }
  37.         //进行times次分配和收集
  38.         for (int i = 0; i < times; i++) {
  39.             //分配
  40.             for (int j = 0; j < array.length; j++) {
  42.                 //每一次比较都把奇数相同的放在同一个队列中，Math.pow(a,b) a的b次方
  43.                 //如果i=2表示取第二位，那么就%100取余 然后/10取取除
  44.                 int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
  46.                 //直接去奇数位置寻找对应的列表
  47.                 ArrayList queue2 = queue.get(x);
  48.                 queue2.add(array[j]);
  50.                 queue.set(x,queue2);
  51.             }
  52.             //收集
  53.             int count = 0;
  54.             for (int j = 0; j < 10; j++) {
  55.                 while(queue.get(j).size()>0){
  56.                     ArrayList<Integer> queue3 = queue.get(j);
  57.                     array[count] = queue3.get(0);
  58.                     queue3.remove(0);
  59.                     count++;
  60.                 }
  61.             }
  62.         }
  63.     }
  64. }

分析

基数排序是稳定的排序算法。

基数排序的时间复杂度为O(d(n+r)),d为位数，r为基数。

总结

一、稳定性:

稳定：冒泡排序、插入排序、归并排序和基数排序

不稳定：选择排序、快速排序、希尔排序、堆排序

二、平均时间复杂度

O(n^2):直接插入排序，简单选择排序，冒泡排序。

在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。

O(nlogn):快速排序，归并排序，希尔排序，堆排序。

其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。

三、排序算法的选择

1.数据规模较小

（1）待排序列基本序的情况下，可以选择直接插入排序；

（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡

2.数据规模不是很大

（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。

（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序

3.数据规模很大

（1）对稳定性有求，则可考虑归并排序。

（2）对稳定性没要求，宜用堆排序

4.序列初始基本有序（正序）

宜用直接插入，冒泡

 116

啊！这个可能是世界上最丑的留言输入框功能~


当然，也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号-2