排序 是我们平时经常需要使用的操作， 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 这里我们介绍七种常用的经典排序，要想理解排序就必须理解每种排序背后的算法思想。 在不同的场景合理地应用不同地排序方法,以便我们能高效地解决问题。

接下来每种排序我都从 算法实现，时间复杂度，空间复杂度，稳定性这几个方面进行阐述。
时间复杂度和空间复杂度是数据结构的基础知识，而稳定性需要着重阐述一下：

即不改变相同数值的内部既定顺序的排序称为稳定排序。

一.直接插入排序:

1.1插入排序

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

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

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

java">/*** 希尔排序(直接插入排序的一种优化)* 首先通过gap对所需排序数据分组进行预排序* gap的取法不一致导致时间复杂度不同* 当gap越大时，每组数据趋于无序，但数据较少* 当gap越小时，每组数据越多，但相较趋于有序* 时间复杂度:就我这种gap取法而言,n*log2n* 			一般来说n^1,3~n^1.5(实验得出）* 空间复杂度:o(1)* 稳定性:不稳定** @param array*/
public static void shellSort(int[] array) {int gap = array.length;//时间复杂度:o(log2n)while (gap > 1) {//在gap>1之前进行的都是预排序gap /= 2;//这里仅仅只gap的一种取法，取法不固定shell(array, gap);//gap可以取到1}}private static void shell(int[] array, int gap) {//shell的时间复杂度大约为o(n)(可以考虑极端情况)for (int i = gap; i < array.length; i++) {//i最后是需要i++的int tmp = array[i];int j = i - gap;for (; j >= 0; j -= gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {array[j + gap] = tmp;break;}}array[j + gap] = tmp;}}

二.选择排序

2.1选择排序

思想简单，但效率不高！

java">/*** 选择排序:* 时间复杂度：o(n^2)* 和数据是否有序无关* 空间复杂度:o(1)* 稳定性:不稳定排序** @param array*/public static void selectSort1(int[] array) {//12,5,2,9,10,7//i jfor (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[i]) {minIndex = j;}}swap(array, i, minIndex);}}public static void selectSort2(int[] array) {//12,5,2,9,10,7//i jint left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array, left, minIndex);//这里有个问题，如果left是最大值的话，它会被交换到minIndex处，则在下一次交换时找不到maxIndexif (left == maxIndex) {maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;}

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

java">/**堆排序(Heapsort):是指利用堆积树（堆）这种数据结构所设计的一种算法>排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆。* 时间复杂度:o(n*logn)* 空间复杂度:o(1)* 稳定性:不稳定* @param array*/public static void heapSort(int[] array){createHeap(array);int end=array.length-1;while(end>0){swap(array,0,end);siftDown(array,0,end);end--;}}private static void createHeap(int[] array) {for(int parent=(array.length-1-1)/2;parent>=0;parent--){siftDown(array,parent,array.length);}}/*** @param array* @param parent 每棵子树调整的根节点* @param length 每棵子树调整的结束节点*/private static void siftDown(int[] array, int parent, int length) {int child=2*parent+1;while(child<length){if(child+1<length&&array[child+1]>array[child]){child++;}if(array[child]>array[parent]){swap(array,parent,child);parent=child;child=2*parent+1;}else{break;}}}

三.交换排序

3.1冒泡排序

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

java">/**冒泡排序:*时间复杂度:o(n^2)---优化前* 优化后可能达到o(n)* 空间复杂度:o(1)* 稳定性:稳定排序* @param array*/public static void bubbleSort(int[] array){//外层循环表示循环趟数for(int i=0;i< array.length-1;i++){boolean flag=false;//优化for(int j=0;j< array.length-1-i;j++){if(array[j]>array[j+1]){swap(array,j,j+1);flag=true;}}if(!flag){break;}}}

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

以递归左边为例子：

快速排序不适用于数据是完全的顺序和逆序的这种极端情况。而适合在数据相对随机的时候使用。因为使用的递归，所以会在栈上开辟空间。

3.1.1Hoare法

java">/*** 时间复杂度：*       最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)*                          9 8 7 6 5 4*       最好情况：O(N*logN)* 空间复杂度：*      最坏情况：O(N)*      最好情况：O(logN)* 稳定性：*      不稳定性* @param array*/public static void quickSort(int[] array){//为了保证接口统一,所以创建quick方法quick(array,0,array.length-1);}private static void quick(int[] array, int start, int end) {if(start>=end)return;int pivot=partitionHoare(array,start,end);//找中间值quick(array,start,pivot-1);//递归左边quick(array,pivot+1,end);//递归右边}private static int partitionHoare(int[] array, int left, int right) {int tmp=array[left];int tmpLeft=left;while(left<right){while(left<right&&array[right]>=tmp){right--;}while(left<right&&array[left]<=tmp){left++;}swap(array,left,right);}swap(array,left,tmpLeft);return left;//return right;}
}

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

前后指针法

四.归并排序

测试代码：

java">public class Test {public static void orderArray(int[] array){for(int i=0;i<array.length;i++){array[i]=i;//顺序//array[i]= array.length-i-1;//逆序}} public static void notorderArray(int[] array){Random random=new Random();for(int i=0;i<array.length;i++){array[i]=random.nextInt(10_0000);}}public static void testSimple(){int[] array={12,5,2,9,10,7};System.out.println("排序前:"+ Arrays.toString(array));Sort.quickSort(array);System.out.println("排序后："+Arrays.toString(array));}public static void testOther(){int[] array=new int[10_0000];//orderArray(array);notorderArray(array);testInsertSort(array);testShellSort(array);testSelectSort1(array);testSelectSort2(array);testHeapSort(array);testBubbleSort(array);testQuickSort(array);}public static void testInsertSort(int[] array){//避免测试后数组本身被修改array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.insertSort(array);long endTime=System.currentTimeMillis();System.out.println("直接插入排序1时间："+(endTime-startTime));}public static void testShellSort(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.shellSort(array);long endTime=System.currentTimeMillis();System.out.println("希尔插入排序时间："+(endTime-startTime));}public static void testSelectSort1(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.selectSort1(array);long endTime=System.currentTimeMillis();System.out.println("选择插入排序1时间："+(endTime-startTime));}public static void testSelectSort2(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.selectSort2(array);long endTime=System.currentTimeMillis();System.out.println("选择插入排序2时间："+(endTime-startTime));}public static void testHeapSort(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.heapSort(array);long endTime=System.currentTimeMillis();System.out.println("堆排序时间："+(endTime-startTime));}public static void testBubbleSort(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.bubbleSort(array);long endTime=System.currentTimeMillis();System.out.println("冒泡排序时间："+(endTime-startTime));}public static void testQuickSort(int[] array){array=Arrays.copyOf(array,array.length);long startTime=System.currentTimeMillis();Sort.quickSort(array);long endTime=System.currentTimeMillis();System.out.println("快速排序时间："+(endTime-startTime));}public static void main(String[] args) {testSimple();testOther();}
}