Java——排序算法

java排序从大的分类来看，可以分为内排序和外排序：其中，在排序过程中只使用了内存的排序称为内排序；内存和外存结合使用的排序成为外排序。

下面讲的都是内排序。

内排序在细分可以这样分：

1、选择排序：直接选择排序，堆排序

2、交换排序：冒泡排序，快速排序

3、插入排序：直接插入排序，二分插入排序，希尔排序

4、归并排序

5、基数排序

是不是觉得这样分类，文字的看着不形象，我也画了一张分类图：

               

通过测试，我的测试数据（后面数据量大了，有的排序时间太长，我就用*代替了）：


通过测试数据来看，不同排序适用于不同的场景，快速排序也不一定是最快的，在数据量比较小的时候，希尔排序反而更快，只是在不断增加数据量的时候，快速排序比较快也很明显。同时，排序也不能只看排序的速度，还需要看它的空间复杂度，即对内存空间利用的要求。例如，快排、归并、堆排序这三者，通过随机数产生数组，它们的时间复杂度可以说是基本一样的，但是当n比较大的时候，你会发现归并排序会比其他两个慢。

各种排序的时间复杂度、空间复杂度和稳定性，同样图形比较形象：

稳定性:
　  1、稳定：冒泡排序、插入排序、归并排序和基数排序
　  2、 不稳定：选择排序、快速排序、希尔排序、堆排序
平均时间复杂度
　　1、O(n^2):直接插入排序，简单选择排序，冒泡排序。
        2、在数据量特别大的时候，冒泡排序基本是最慢的。
　　3、在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本
上是相邻元素进行比较，基本上都是稳定的。
　　1、O(nlogn):快速排序，归并排序，希尔排序，堆排序。
　　2、其中，快排是最好的， 其次是归并和希尔，但数据量特别大的时候，归并排序很容易出现内存溢出的错误，如普通机器n>1000万时。
空间复杂度
         1、O(1):冒泡排序、直接插入排序、二分插入排序、希尔排序、直接选择排序、堆排序
         2、 O(n):归并排序
         3、 O(nlog2n):快速排序
         4、O(rd+n）:基数排序
排序算法的选择
　　1、数据规模较小
  　 （1）待排序列基本序的情况下，可以选择直接插入排序；
  　 （2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
　　2、数据规模不是很大
　   （1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
　   （2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
　　 3、数据规模很大
        （1）对稳定性有求，则可考虑归并排序。
        （2）对稳定性没要求，可以用快速排序。
　　4、数组初始基本有序的时候，宜用直接插入排序，否则，可以用希尔排序。

下面是实现源码：

[java] view plain copy
 
  1. package sort;  
  2.   
  3. /**   
  4.  * Package: sort   
  5.  *   
  6.  * File: JavaSorts.java    
  7.  *   
  8.  * Copyright @ 2015 Corpration Name   
  9.  *    
  10.  */  
  11. public class JavaSorts {  
  12.   
  13.     /** 
  14.      * 希尔排序 
  15.      * @param array 
  16.      */  
  17.     public static void ShellSort(int[] array){  
  18.         int d = array.length;  
  19.         do {  
  20.             d /= 2;   //设置增量,通过设置增量来进行分组，分组后，每一组内采用直接插入排序  
  21.             OneShell(array, d);//一个增量对应一趟希尔排序  
  22.         } while (d > 1);  
  23.     }  
  24.       
  25.     /** 
  26.      * 一趟希尔排序 
  27.      * @param array 
  28.      * @param d 
  29.      */  
  30.     public static void OneShell(int[] array,int d){  
  31.           
  32.         for (int i = 0; i < array.length - d; i++) {  
  33.             int temp = array[i+d]; //array[i+d]的拷贝，每一次插入操作所以插入的值  
  34.             if (array[i] > array[i + d]) {  
  35.                 int j = i;  
  36.                 //此时分组为：j,j+d,j+2d,j+3d····,组内采用直接插入排序  
  37.                 while(j >= 0 && array[j] > temp){  
  38.                     array[j + d] = array[j];    //使用while循环寻找temp能够插入的位置，从右往左寻找，大于temp的往后移动  
  39.                     j -= d;  
  40.                 }  
  41.                 array[j + d] = temp;   //插入数据  
  42.             }  
  43.         }     
  44.     }  
  45.       
  46.     /** 
  47.      * 快速排序 
  48.      * @param array 
  49.      * @param l 
  50.      * @param r 
  51.      */  
  52.     public static void QuickSort(int[] array,int l,int r){  
  53.         if (l < r) {  
  54.             int i = l,j = r,temp = array[l];  
  55.             while(i < j){  
  56.                 while(i < j && array[j] > temp){  
  57.                     j--;         //从右边开始寻找比temp小的数  
  58.                 }  
  59.                 if(i < j){  
  60.                     array[i++] = array[j]; //找到后，将这个数赋值到i位置上,然后i+1,因为下一轮寻找比temp大的数，从i+1位置开始  
  61.                 }  
  62.                 while(i < j && array[i] < temp){  
  63.                     i++;          //从左边寻找比temp大的数  
  64.                 }  
  65.                 if(i < j){  
  66.                     array[j--] = array[i]; //找到后，将这个数赋值到j位置上，然后j-1,因为下一轮寻找比temp小的数从j-1位置开始  
  67.                 }  
  68.             }  
  69.             array[i] = temp;  //此时比temp小的数都移动到左边，比temp大的数都移动到了右边，最后将temp赋值到中间位置  
  70.               
  71.             QuickSort(array, l, i - 1); //对temp左边的数进行递归  
  72.             QuickSort(array, i + 1, r); //对temp右边的数进行递归  
  73.         }  
  74.     }  
  75.       
  76.     /** 
  77.      * 堆排序 
  78.      * @param array 
  79.      */  
  80.     public static void HeapSort(int[] array){  
  81.         for (int i = 0; i < array.length; i++) {  
  82.             BuildMaxHeap(array, array.length - 1 - i);  
  83.             Swap(array, 0, array.length - 1 - i);  
  84.         }  
  85.     }  
  86.     /** 
  87.      * 创建最大堆 
  88.      * @param array 
  89.      * @param lastOneIndex 
  90.      */  
  91.     public static void BuildMaxHeap(int[] array,int lastOneIndex){  
  92.           
  93.         for (int i = (lastOneIndex - 1)/2; i >= 0; i--) {  
  94.             int k = i;  
  95.             while(2*k + 1 <= lastOneIndex){  
  96.                 int bigIndex = 2*k + 1;   //bigIndex用于记录一个节点树中最大数的索引  
  97.                 if (bigIndex < lastOneIndex) {  //满足这个条件，说明堆中有array[2*k+2]这个节点  
  98.                     if (array[bigIndex] < array[bigIndex + 1]) {  
  99.                         bigIndex++;      //若满足这个条件，说明k节点下的右子节点大于左子结点，因而bigIndex加1  
  100.                     }  
  101.                 }  
  102.                   
  103.                 if (array[k] < array[bigIndex]) {  
  104.                     Swap(array, bigIndex, k); //若k节点小于它其中一个子节点，则与这个子节点交换值  
  105.                     k = bigIndex;  //交换完值后，此时k节点下面的bigIndex节点可能不满足堆的性质，所以赋值给k,重新进入下一轮while循环  
  106.                 }else {  
  107.                     break;//若k节点满足堆的性质，则直接跳出循环  
  108.                 }  
  109.             }  
  110.         }  
  111.           
  112.     }  
  113.       
  114.     /** 
  115.      * 交换array中array[a]、array[b] 
  116.      * @param array 
  117.      * @param a 
  118.      * @param b 
  119.      */  
  120.     public static void Swap(int[] array,int a,int b){  
  121.         if (a < array.length && b < array.length) {  
  122.             int temp = array[a];  
  123.             array[a] = array[b];  
  124.             array[b] = temp;  
  125.         }  
  126.     }  
  127.       
  128.     /** 
  129.      * 直接插入排序 
  130.      * @param array 
  131.      */  
  132.     public static void DirectInsertSort(int[] array){  
  133.         for (int i = 0; i < array.length - 1; i++) {  
  134.             int temp = array[i + 1];  
  135.             if (array[i] > array[i + 1]) {  
  136.                 int j = i;  
  137.                 while(j >= 0 && array[j] > temp){  
  138.                     array[j + 1] = array[j];  
  139.                     j--;  
  140.                 }  
  141.                 array[j + 1] = temp;  
  142.             }  
  143.         }  
  144.     }  
  145.       
  146.     /** 
  147.      * 二分插入排序 
  148.      * @param array 
  149.      */  
  150.     public static void BinaryInsertSort(int[] array){  
  151.         for (int i = 0; i < array.length - 1; i++) {  
  152.             int temp = array[i + 1];  //需要插入的数  
  153.             if(array[i] > array[i + 1]){  
  154.                 int l = 0;   //有序队列中左边标识  
  155.                 int r = i;   //有序队列中右边标识  
  156.                 while(l < r){  
  157.                     int mid = (l + r) / 2; //永远指向l->r中间的那个值，中间值与temp(需要插入的值)比较  
  158.                     if (array[mid] > temp) {  
  159.                         r--;              //通过while循环，二分折半搜索temp应该插入的位置  
  160.                     }else {  
  161.                         l++;  
  162.                     }  
  163.                 }  
  164.                 //运行到这里，l==r,即是temp应该插入的位置是array[l](或者array[r])  
  165.                 for (int j = i + 1; j > l; j--) {     
  166.                     array[j] = array[j - 1];  //将l -> i的数都往后移动一位  
  167.                 }  
  168.                 array[l] = temp;  //将temp插入到l位置  
  169.                   
  170.             }  
  171.                   
  172.             }  
  173.     }  
  174.     /** 
  175.      * 直接选择排序 
  176.      * @param array 
  177.      */  
  178.     public static void DirectSelectSort(int[] array){  
  179.         for (int i = 0; i < array.length - 1; i++) {  
  180.             int min = array[i];  
  181.             for (int j = i + 1; j < array.length; j++) {  
  182.                 if (array[j] < min) {  
  183.                     min = array[j];  
  184.                     array[j] = array[i];  
  185.                     array[i] = min;  
  186.                 }  
  187.             }  
  188.         }  
  189.     }  
  190.     /** 
  191.      * 冒泡排序 
  192.      * @param array 
  193.      */  
  194.     public static void BubbleSort(int[] array){  
  195.         int temp = 0;  
  196.         for (int i = 0; i < array.length; i++) {  
  197.             for (int j = 0; j < array.length - 1; j++) {  
  198.                 if (array[j] > array[j+1]) {  
  199.                     temp = array[j];  
  200.                     array[j] = array[j+1];    
  201.                     array[j+1] = temp;  
  202.                 }  
  203.             }  
  204.         }  
  205.     }  
  206.       
  207.     /** 
  208.      * 归并排序 
  209.      * @param array 
  210.      */  
  211.     public static void MergeSort(int[] array){  
  212.         int left = 0;  
  213.         int right = array.length - 1;  
  214.         MergeSortRecursive(array, left, right);  
  215.     }  
  216.     /** 
  217.      * 归并排序的递归方法 
  218.      * @param array 
  219.      * @param left 
  220.      * @param right 
  221.      */  
  222.     public static void MergeSortRecursive(int[] array,int left,int right){  
  223.         if (left >= right) {  
  224.             return;  //递归的停止判断，没有这个判断会报StackOverflowError  
  225.         }  
  226.         int mid = (left + right)/2;  
  227.         MergeSortRecursive(array, left, mid);  
  228.         MergeSortRecursive(array, mid+1, right);  
  229.         Merge(array, left, mid, right);  
  230.     }  
  231.       
  232.     /** 
  233.      * 归并排序中合并方法 
  234.      * @param array 
  235.      * @param left 
  236.      * @param mid 
  237.      * @param right 
  238.      */  
  239.     public static void Merge(int[] array,int left,int mid,int right){  
  240.         int r_left = mid + 1; //需要合并数组中右边数组第一个数索引  
  241.         int[] tempArray = new int[array.length];//一个临时数组，用于合并时暂时存储  
  242.         int newIndex = left;   //临时数组索引  
  243.         int tempLeft = left;   //合并完了以后，用于复制数组的索引  
  244.         while(left <= mid && r_left <= right){   //将部分的数放入到临时数组中  
  245.             if (array[left] < array[r_left]) {  
  246.                 tempArray[newIndex++] = array[left++];  
  247.             }else {  
  248.                 tempArray[newIndex++] = array[r_left++];  
  249.             }  
  250.         }  
  251.         while (left <= mid) {  
  252.             tempArray[newIndex++] = array[left++];  //将左边还剩余的数放入临时数组(若需要合并的左边还剩余数)  
  253.         }  
  254.           
  255.         while(r_left <= right){  
  256.             tempArray[newIndex++] = array[r_left++];//将右边还剩余的数放入临时数组(若需要和并的右边还剩余数)  
  257.         }  
  258.         while(tempLeft <= right){  
  259.             array[tempLeft] = tempArray[tempLeft++];  //将临时数组复制到array  
  260.         }  
  261.     }  
  262.       
  263.     /** 
  264.      * 基数排序 
  265.      * @param array 
  266.      */  
  267.     public static void RadixSort(int[] array){  
  268.         int bits = FindMaxBit(array);  //得到数组中最大的那个数的位数  
  269.         for (int i = 0; i < bits; i++) {  
  270.             OneBitSort(array, i+1);  //一位基数的排序  
  271.         }  
  272.     }  
  273.     /** 
  274.      * 一位基数的排序 
  275.      * @param array 
  276.      * @param bit 
  277.      */  
  278.     public static void OneBitSort(int[] array,int bit){  
  279.         int[] tempArray = new int[array.length];  
  280.         int index = 0;  
  281.         int tempIndex = 0;  
  282.         for (int i = 0; i < 10; i++) {  
  283.             for (int j = 0; j < array.length; j++) {  
  284.                 if (FindBitNum(array[j], bit) == i) {  
  285.                     tempArray[index++] = array[j];  
  286.                 }  
  287.             }  
  288.         }  
  289.         while(tempIndex < array.length){  
  290.             array[tempIndex] = tempArray[tempIndex++]; //复制数组  
  291.         }  
  292.     }  
  293.     /** 
  294.      * 得到某个数某一位的数(例如：num=1234,n=2,FindBitNum(1234,2)=3) 
  295.      * @param num 
  296.      * @param n 
  297.      * @return 
  298.      */  
  299.     public static int FindBitNum(int num,int n){  
  300.         int key1 = (int)Math.pow(10, n);  
  301.         int key2 = (int)Math.pow(10, n-1);  
  302.         num %= key1;  
  303.         num /= key2;  
  304.         return num;  
  305.     }  
  306.     /** 
  307.      * 得到一个数组中最大数的位数 
  308.      * @param array 
  309.      * @return 
  310.      */  
  311.     public static int FindMaxBit(int[] array){  
  312.           
  313.         if (array == null || array.length ==0) {  
  314.             return 0;  
  315.         }  
  316.         int max = array[0];  
  317.         for (int i = 1; i < array.length; i++) {  
  318.             if (array[i] > max) {  
  319.                 max = array[i];  
  320.             }  
  321.         }  
  322.         int bit = 0;  
  323.         while(max / 10 != 0 || max % 10 != 0){  
  324.             max /= 10;  
  325.             bit++;  
  326.         }  
  327.         return bit;  
  328.           
  329.     }  
  330.     public static void main(String[] args) {  
  331.           
  332.         System.out.println("冒泡排序："+SortThreads.getBubbleSortTime());  
  333.         System.out.println("直接选择排序："+SortThreads.getDirSelectSortTime());  
  334.         System.out.println("直接插入排序："+SortThreads.getDirInsertSortTime());  
  335.         System.out.println("二分插入排序："+SortThreads.getBinaryInsertSortTime());  
  336.         System.out.println("快速排序："+SortThreads.getQuickSortTime());  
  337.         System.out.println("希尔排序："+SortThreads.getShellSortTime());  
  338.         System.out.println("归并排序："+SortThreads.getMergeSortTime());  
  339.         System.out.println("基数排序："+SortThreads.getRadixSortTime());  
  340.         System.out.println("堆排序："+SortThreads.getHeapSortTime());  
  341.           
  342.           
  343.     }  
  344. }  

对于这些排序算法，我对它们的排序速度比较感兴趣，所以自己也测试了一下，数组是通过随机数产生的，我测的时候每一个数是不大于4位数，即不大于10000。

ProduceRandomNum.java产生随机数的数组：

[java] view plain copy
 
  1. package sort;  
  2.   
  3. import java.util.Random;  
  4.   
  5. /**   
  6.  * Package: sort   
  7.  *   
  8.  * File: SortRunnable.java    
  9.  *   
  10.  * Copyright @ 2015 Corpration Name   
  11.  *    
  12.  */  
  13. public class ProduceRandomNum{  
  14.   
  15.     public synchronized static int[] RandomArray(int num,int n){  
  16.         Random random = new Random();  
  17.         int[] array = new int[num];  
  18.         for (int i = 0; i < array.length; i++) {  
  19.             array[i] = random.nextInt((int)Math.pow(10, n));  
  20.         }  
  21.         return array;  
  22.     }  
  23.       
  24.   
  25. }  

SortThreads.java测试排序的时间的方法，封装都一个类中，这个类我一直想把它写成多线程的方式（即是将这些排序一起运行），但是后面没有找到一个好的方法，所以后面就用了这种最笨的方法，有好办法的大神一定要指出来。

[java] view plain copy
 
  1. package sort;  
  2. /**   
  3.  * Package: sort   
  4.  *   
  5.  * File: SortThreads.java    
  6.  *   
  7.  * Copyright @ 2015 Corpration Name   
  8.  *    
  9.  */  
  10. public class SortThreads {  
  11.   
  12.     private static final int arrayNum = 500000;  
  13.     private static final int bit = 4;  
  14.     public static long getBubbleSortTime(){  
  15.         long oldTime = System.currentTimeMillis();  
  16.         JavaSorts.BubbleSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  17.         long newTime = System.currentTimeMillis();  
  18.         return newTime - oldTime;  
  19.     }  
  20.     public static long getQuickSortTime(){  
  21.         int[] array = ProduceRandomNum.RandomArray(arrayNum, bit);  
  22.         long oldTime = System.currentTimeMillis();  
  23.         JavaSorts.QuickSort(array, 0, array.length - 1);  
  24.         long newTime = System.currentTimeMillis();  
  25.         return newTime - oldTime;  
  26.     }  
  27.     public static long getDirSelectSortTime(){  
  28.         long oldTime = System.currentTimeMillis();  
  29.         JavaSorts.DirectSelectSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  30.         long newTime = System.currentTimeMillis();  
  31.         return newTime - oldTime;  
  32.     }  
  33.     public static long getDirInsertSortTime(){  
  34.         long oldTime = System.currentTimeMillis();  
  35.         JavaSorts.DirectInsertSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  36.         long newTime = System.currentTimeMillis();  
  37.         return newTime - oldTime;  
  38.     }  
  39.       
  40.     public static long getBinaryInsertSortTime(){  
  41.         long oldTime = System.currentTimeMillis();  
  42.         JavaSorts.BinaryInsertSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  43.         long newTime = System.currentTimeMillis();  
  44.         return newTime - oldTime;  
  45.     }  
  46.       
  47.     public static long getShellSortTime(){  
  48.         long oldTime = System.currentTimeMillis();  
  49.         JavaSorts.ShellSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  50.         long newTime = System.currentTimeMillis();  
  51.         return newTime - oldTime;  
  52.     }  
  53.     public static long getMergeSortTime(){  
  54.         long oldTime = System.currentTimeMillis();  
  55.         JavaSorts.MergeSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  56.         long newTime = System.currentTimeMillis();  
  57.         return newTime - oldTime;  
  58.     }  
  59.     public static long getRadixSortTime(){  
  60.         long oldTime = System.currentTimeMillis();  
  61.         JavaSorts.RadixSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  62.         long newTime = System.currentTimeMillis();  
  63.         return newTime - oldTime;  
  64.     }  
  65.     public static long getHeapSortTime(){  
  66.         long oldTime = System.currentTimeMillis();  
  67.         JavaSorts.HeapSort(ProduceRandomNum.RandomArray(arrayNum, bit));  
  68.         long newTime = System.currentTimeMillis();  
  69.         return newTime - oldTime;  
  70.     }  
  71. }  

转载：https://blog.csdn.net/u014039577/article/details/49667643

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yuzijian/p/9199101.html