七大经典基于比较排序算法【Java实现】

排序 是我们平常常常需要使用的操作， 所谓排序，就是使一串记录，按照此中的某个或某些关键字的大小，递增或递减的排列起来的操作。 这里我们先容七种常用的经典排序，要想明白排序就必须明白每种排序背后的算法思想。 在不同的场景合理地应用不同地排序方法,以便我们能高效地办理标题。
  接下来每种排序我都从 算法实现，时间复杂度，空间复杂度，稳定性这几个方面进行阐述。
时间复杂度和空间复杂度是数据结构的基础知识，而稳定性需要偏重阐述一下：

   即不改变相同数值的内部既定次序的排序称为稳定排序。
  一.直接插入排序:

1.1插入排序

1. /** 时间复杂度:o(n^2)
2.          最坏情况：5 4 3 2 1
3.          最好情况: 1 2 3 4 5 o(n)
4.          如果一组数据越有序，则直接插入排序效率越高
5.          空间复杂度:o(1)
6.          稳定性：稳定排序（>)
7.          如果一个排序本身是稳定的，那么他可以实现为不稳定的
8.          若是不稳定的，则它不能实现为稳定的
9.          *
10.          */
11.         //默认从小到大,第一个数字默认有序
12. public static void insertSort(int[] array) {
13.         for (int i = 1; i < array.length; i++) {
14.             int tmp = array[i];
15.             int j = i - 1;
16.             for (; j >= 0; j--) {
17.                 if (array[j] > tmp) {
18.                     array[j + 1] = array[j];
19.                 } else {
20.                     array[j + 1] = tmp;
21.                     break;
22.                 }
23.             }
24.             array[j + 1] = tmp;
25.         }
26.     }

复制代码

1.2希尔排序（缩小增量排序法）

   希尔排序可视为直接插入排序的一种优化，其本质是将数据分为多组别，在不同组别内部进行插入排序，随着组别数减少，组别内数据元素趋于有序，效率加快。

1. /**
2.      * 希尔排序(直接插入排序的一种优化)
3.      * 首先通过gap对所需排序数据分组进行预排序
4.      * gap的取法不一致导致时间复杂度不同
5.      * 当gap越大时，每组数据趋于无序，但数据较少
6.      * 当gap越小时，每组数据越多，但相较趋于有序
7.      * 时间复杂度:就我这种gap取法而言,n*log2n
8.      *                         一般来说n^1,3~n^1.5(实验得出）
9.      * 空间复杂度:o(1)
10.      * 稳定性:不稳定
11.      *
12.      * @param array
13.      */
14. public static void shellSort(int[] array) {
15.         int gap = array.length;
16.         //时间复杂度:o(log2n)
17.         while (gap > 1) {
18.             //在gap>1之前进行的都是预排序
19.             gap /= 2;//这里仅仅只gap的一种取法，取法不固定
20.             shell(array, gap);//gap可以取到1
21.         }
22.     }
24.     private static void shell(int[] array, int gap) {
25.         //shell的时间复杂度大约为o(n)(可以考虑极端情况)
26.         for (int i = gap; i < array.length; i++) {
27.             //i最后是需要i++的
28.             int tmp = array[i];
29.             int j = i - gap;
30.             for (; j >= 0; j -= gap) {
31.                 if (array[j] > tmp) {
32.                     array[j + gap] = array[j];
33.                 } else {
34.                     array[j + gap] = tmp;
35.                     break;
36.                 }
37.             }
38.             array[j + gap] = tmp;
39.         }
40.     }

复制代码

二.选择排序

2.1选择排序

   思想简单，但效率不高！

1. /**
2.      * 选择排序:
3.      * 时间复杂度：o(n^2)
4.      * 和数据是否有序无关
5.      * 空间复杂度:o(1)
6.      * 稳定性:不稳定排序
7.      *
8.      * @param array
9.      */
10.     public static void selectSort1(int[] array) {
11.         //12,5,2,9,10,7
12.         //i j
14.         for (int i = 0; i < array.length; i++) {
15.             int minIndex = i;
16.             for (int j = i + 1; j < array.length; j++) {
17.                 if (array[j] < array[i]) {
18.                     minIndex = j;
19.                 }
20.             }
21.             swap(array, i, minIndex);
22.         }
23.     }
24.     public static void selectSort2(int[] array) {
25.         //12,5,2,9,10,7
26.         //i j
27.         int left = 0;
28.         int right = array.length - 1;
29.         while (left < right) {
30.             int minIndex = left;
31.             int maxIndex = left;
32.             for (int i = left + 1; i <= right; i++) {
33.                 if (array[i] < array[minIndex]) {
34.                     minIndex = i;
35.                 }
36.                 if (array[i] > array[maxIndex]) {
37.                     maxIndex = i;
38.                 }
39.             }
40.             swap(array, left, minIndex);
41.             //这里有个问题，如果left是最大值的话，它会被交换到minIndex处，则在下一次交换时找不到maxIndex
42.             if (left == maxIndex) {
43.                 maxIndex = minIndex;
44.             }
45.             swap(array, right, maxIndex);
46.             left++;
47.             right--;
48.         }
49.     }
51.     private static void swap(int[] array, int i, int minIndex) {
52.         int tmp = array[i];
53.         array[i] = array[minIndex];
54.         array[minIndex] = tmp;
55.     }

复制代码

2.2堆排序（基于树（堆）的数据结构）

1. /**堆排序(Heapsort):是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆
2.      来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆。
3.      * 时间复杂度:o(n*logn)
4.      * 空间复杂度:o(1)
5.      * 稳定性:不稳定
6.      * @param array
7.      */
8.     public static void heapSort(int[] array){
9.         createHeap(array);
10.         int end=array.length-1;
11.         while(end>0){
12.             swap(array,0,end);
13.             siftDown(array,0,end);
14.             end--;
15.         }
16.     }
18.     private static void createHeap(int[] array) {
19.         for(int parent=(array.length-1-1)/2;parent>=0;parent--){
20.             siftDown(array,parent,array.length);
21.         }
22.     }
23.     /**
24.      * @param array
25.      * @param parent 每棵子树调整的根节点
26.      * @param length 每棵子树调整的结束节点
27.      */
28.     private static void siftDown(int[] array, int parent, int length) {
29.         int child=2*parent+1;
30.         while(child<length){
31.             if(child+1<length&&array[child+1]>array[child]){
32.                 child++;
33.             }
34.             if(array[child]>array[parent]){
35.                 swap(array,parent,child);
36.                 parent=child;
37.                 child=2*parent+1;
38.             }else{
39.                 break;
40.             }
41.         }
42.     }

复制代码

三.互换排序

3.1冒泡排序

   最大（小）的数据不停移动到数据末了，就像水泡一样浮出水面。

1. /**冒泡排序:
2.      *时间复杂度:o(n^2)---优化前
3.      * 优化后可能达到o(n)
4.      * 空间复杂度:o(1)
5.      * 稳定性:稳定排序
6.      * @param array
7.      */
8.     public static void bubbleSort(int[] array){
9.     //外层循环表示循环趟数
10.         for(int i=0;i< array.length-1;i++){
11.             boolean flag=false;//优化
12.             for(int j=0;j< array.length-1-i;j++){
13.                 if(array[j]>array[j+1]){
14.                     swap(array,j,j+1);
15.                     flag=true;
16.                 }
17.             }
18.             if(!flag){
19.                 break;
20.             }
21.         }
22.     }

复制代码

3.1快速排序(大致分三种partition方法)

以递归左边为例子：

   快速排序不实用于数据是完全的次序和逆序的这种极端环境。而适合在数据相对随机的时间使用。由于使用的递归，所以会在栈上开辟空间。
  3.1.1Hoare法

1. /**
2.      * 时间复杂度：
3.      *       最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)
4.      *                          9 8 7 6 5 4
5.      *       最好情况：O(N*logN)
6.      * 空间复杂度：
7.      *      最坏情况：O(N)
8.      *      最好情况：O(logN)
9.      * 稳定性：
10.      *      不稳定性
11.      * @param array
12.      */
13.     public static void quickSort(int[] array){
14.         //为了保证接口统一,所以创建quick方法
15.         quick(array,0,array.length-1);
16.     }
18.     private static void quick(int[] array, int start, int end) {
19.         if(start>=end)return;
20.         int pivot=partitionHoare(array,start,end);//找中间值
21.         quick(array,start,pivot-1);//递归左边
22.         quick(array,pivot+1,end);//递归右边
23.     }
25.     private static int partitionHoare(int[] array, int left, int right) {
26.         int tmp=array[left];
27.         int tmpLeft=left;
28.         while(left<right){
29.             while(left<right&&array[right]>=tmp){
30.                 right--;
31.             }
32.             while(left<right&&array[left]<=tmp){
33.                 left++;
34.             }
35.             swap(array,left,right);
36.         }
37.         swap(array,left,tmpLeft);
38.         return left;
39.         //return right;
40.     }
41. }

复制代码

挖坑法（最常用，选择题首选)

前后指针法

四.归并排序

测试代码：

1. public class Test {
2.     public static void orderArray(int[] array){
3.         for(int i=0;i<array.length;i++){
4.             array[i]=i;//顺序
5.             //array[i]= array.length-i-1;//逆序
6.         }
7.     } public static void notorderArray(int[] array){
8.         Random random=new Random();
9.         for(int i=0;i<array.length;i++){
10.             array[i]=random.nextInt(10_0000);
11.         }
12.     }
13.     public static void testSimple(){
14.         int[] array={12,5,2,9,10,7};
15.         System.out.println("排序前:"+ Arrays.toString(array));
16.         Sort.quickSort(array);
17.         System.out.println("排序后："+Arrays.toString(array));
18.     }
19.     public static void testOther(){
20.         int[] array=new int[10_0000];
21.         //orderArray(array);
22.         notorderArray(array);
23.         testInsertSort(array);
24.         testShellSort(array);
25.         testSelectSort1(array);
26.         testSelectSort2(array);
27.         testHeapSort(array);
28.         testBubbleSort(array);
29.         testQuickSort(array);
30.     }
31.     public static void testInsertSort(int[] array){
32.         //避免测试后数组本身被修改
33.         array=Arrays.copyOf(array,array.length);
34.         long startTime=System.currentTimeMillis();
35.         Sort.insertSort(array);
36.         long endTime=System.currentTimeMillis();
37.         System.out.println("直接插入排序1时间："+(endTime-startTime));
38.     }
39.     public static void testShellSort(int[] array){
40.         array=Arrays.copyOf(array,array.length);
41.         long startTime=System.currentTimeMillis();
42.         Sort.shellSort(array);
43.         long endTime=System.currentTimeMillis();
44.         System.out.println("希尔插入排序时间："+(endTime-startTime));
45.     }
46.     public static void testSelectSort1(int[] array){
47.         array=Arrays.copyOf(array,array.length);
48.         long startTime=System.currentTimeMillis();
49.         Sort.selectSort1(array);
50.         long endTime=System.currentTimeMillis();
51.         System.out.println("选择插入排序1时间："+(endTime-startTime));
52.     }
53.     public static void testSelectSort2(int[] array){
54.         array=Arrays.copyOf(array,array.length);
55.         long startTime=System.currentTimeMillis();
56.         Sort.selectSort2(array);
57.         long endTime=System.currentTimeMillis();
58.         System.out.println("选择插入排序2时间："+(endTime-startTime));
59.     }
60.     public static void testHeapSort(int[] array){
61.         array=Arrays.copyOf(array,array.length);
62.         long startTime=System.currentTimeMillis();
63.         Sort.heapSort(array);
64.         long endTime=System.currentTimeMillis();
65.         System.out.println("堆排序时间："+(endTime-startTime));
66.     }
67.     public static void testBubbleSort(int[] array){
68.         array=Arrays.copyOf(array,array.length);
69.         long startTime=System.currentTimeMillis();
70.         Sort.bubbleSort(array);
71.         long endTime=System.currentTimeMillis();
72.         System.out.println("冒泡排序时间："+(endTime-startTime));
73.     }
74.     public static void testQuickSort(int[] array){
75.         array=Arrays.copyOf(array,array.length);
76.         long startTime=System.currentTimeMillis();
77.         Sort.quickSort(array);
78.         long endTime=System.currentTimeMillis();
79.         System.out.println("快速排序时间："+(endTime-startTime));
80.     }
81.     public static void main(String[] args) {
82.         testSimple();
83.         testOther();
84.     }
85. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。