详解常见排序
目录
声明：以下排序代码由Java实现！！！
插入排序
步骤：
1.我们可以认为数组的第一个元素已经被排好序，因此只需考虑对后面的元素进行插入排序；
2.取下一个位置的元素val，让它和它之前的元素进行比较，顺序为从右向左；
3.如果该元素大于val，则将该元素移动到该元素所处位置的下一个位置；
4.重复步骤3，知道找到已排好序的序列中小于等于val的元素；
5.将值val放到该位置的下一个位置，如果已排好序的所有元素的值都大于val，则将val存放到数组下标为0的位置；
6.重复2~5步骤。
动画演示：
代码如下：
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 break; } array[j+1]=tmp; } }折半插入排序
在该值为val的元素找合适的位置时，是在已排好序的序列中进行找的，因此该过程可以使用二分查找（折半查找）来进行优化。
代码如下：
public static void bsInsertSort(int[] array){ for(int i=0;i<array.length;i++){ int tmp=array[i]; int left=0,right=i; while(left<right){ int mid=(left+right)>>1; if(tmp>=array[mid]) left=mid+1; else right=mid; } for(int j=i;j>left;j--) array[j]=array[j-1]; array[left]=tmp; } }时间复杂度：最好情况下为O(N)，此时待排数组为升序，或者说非常接近升序；
最坏情况下为O(N^N)，此时待排数组为降序，或者说非常接近降序。
空间复杂度：O(1)
稳定性：稳定
希尔排序（缩小增量排序）
思想：
先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素划分在同一组，对每组的元素进行直接插入排序，然后再选取一个比第一增量小的整数作为第二增量gap，然后将所有距离为gap的元素划分在同一组，对每组的元素进行直接插入排序，以此类推.........，直到增量减小为1时，此时就相当于整个数组被划分为一组，进行一次直接插入排序即可。
增量gap大于1时，称为“预排序”，使得待排数组接近有序；增量gap为1时，称为直接插入排序。
动画演示
代码如下：
public static void shellSort(int[] array){ int gap=array.length; while(gap>1){ gap=gap/3+1; shell(array,gap); } } private static void shell(int[] array,int gap){ for(int i=gap;i<array.length;i++){ int tmp=array[i]; int j=i-gap; for(;j>=0;j-=gap){ if(array[j]>tmp) array[j+gap]=array[j]; else break; } array[j+gap]=tmp; } }平均时间复杂度：O(N^1.3)
空间复杂度：O(1)
选择排序
每一次从待排序列中选出最小（或者最大）的一个元素，存放在待排序列的起始位置，同时将待排序列原来起始位置的值放到待排序列中最小元素的位置，直到待排数据全部排完序。
动画演示
代码如下：
public static void selectSort(int[] array){ for(int i=0;i<array.length;i++){ int minIndex=i; for(int j=i+1;j<array.length;j++) if(array[j]<array[minIndex]) minIndex=j; swap(array,i,minIndex); } } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }实际上，我们可以每一趟同时选择出待排序列中的最小值和最大值，然后将最小值放待排序列起始位置，将最大值放到待排序列的末尾，直到待排数据全部排完序，这样的话比前一种方法快一倍。
代码如下：
public static void DoubleSelectSort(int[] array){ int left=0,right=array.length-1; while(left<right){ int minIndex=left,maxIndex=left; for(int i=left+1;i<=right;i++){ if(array[i]>array[maxIndex]) maxIndex=i; if(array[i]<array[minIndex]) minIndex=i; } swap(array,left,minIndex); if(maxIndex==left) maxIndex=minIndex; swap(array,right,maxIndex); left++; right--; } } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }时间复杂度：O(N^2)
空间复杂度：O(1)
冒泡排序
进行N趟，每一趟中，如果前一个位置的元素大于后一个位置的元素，则交换两个位置的元素。
动画演示
代码如下：
public static void bubbleSort(int[] array){ for(int i=0;i<array.length;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; } }时间复杂度：O(N^2)
空间复杂度：O(1)
堆排序
排升序建大根堆，排降序建小根堆。
以排升序为例，先对数组建立大根堆，然后将堆顶元素和堆最后一个元素交换，然后从堆顶进行向下调整，不过此时堆的大小要 -1，因为已经把最大的元素找出来并放在数组的末尾了，不断重复上述操作，直到将整个数组的元素排完序。
动画演示：
代码如下：
public static void heapSort(int[] array){ createBigHeap(array); int end=array.length-1; while(end>0){ swap(array,0,end); shiftDown(array,0,end); end--; } } private static void createBigHeap(int[] array){ for(int parent=array.length-1-1;parent>=0;parent--) shiftDown(array,parent,array.length); } private static void shiftDown(int[] array,int parent,int end){ int child=2*parent+1; while(child<end){ if(child+1<end && array[child+1]>array[child]) child++; if(array[parent]<array[child]){ swap(array,parent,child); parent=child; child=2*parent+1; } else break; } } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }时间复杂度：O(N*logN)
空间复杂度：O(1)
快速排序
hoare版
步骤：
1.选定一个值Key，下标记为Keyi，通常是最左边的元素或者最右边的元素；
2.定义两个指针begin和end，being从左往右走，end从右往左走;
3.若选定的Key值是最左边的元素，需要end先走，若选定的Key值是最右边的元素，需要begin先走;
4.在走的过程中，当end遇到小于Key的数，才停下；然后begin开始走，直到遇到大于Key的数，然后交换位于begin和end位置的值，然后end再走，规则如上，直到begin和end相遇，此时再将位于Keyi位置的Key值和begin和end相遇点的值进行交换；
5.此时，Key左边的值都是小于等于Key的数，Key右边的值都是大于等于Key的数；
6.然后再对Key左边的数以及Key右边的数分别进行如上操作，直到待排序列只有一个元素为止。
动画演示：
代码如下：
因为该方法包含大量的递归，当数据量较大时会发生栈溢出，因此做一些优化，包括【三数取中】和【当待排区间长度小于某个常数时，不再递归进行快排，而是使用直接插入排序】
public static void quickSort(int[] array){ quick(array,0,array.length-1); } private static void quick(int[] array,int start,int end){ if(start>=end) return; if(end-start<=7){ insertSortRange(array,start,end); return; } int pivot=partitionHoare(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } private static void insertSortRange(int[] array,int begin,int end) { for (int i = begin+1; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= begin ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static int midOfThree(int[] array, int left, int right) { int mid = (left+right) / 2; if(array[left] < array[right]) { if(array[mid] < array[left]) { return left; }else if(array[mid] > array[right]) { return right; }else { return mid; } }else { if(array[mid] > array[left]) { return left; }else if(array[mid] < array[right]) { return right; }else { return mid; } } } private static int partitionHoare(int[] array,int left,int right){ int key=array[left]; int keyi=left; while(left<right){ while(left<right && array[right]>=key) right--; while(left<right && array[left]<=key) left++; swap(array,left,right); } swap(array,keyi,left); return left; } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }时间复杂度：O(N*logN)
空间复杂度：O(1)
挖坑法
步骤：
1.选定一个Key值，通常是位于最左边或者是最右边，在该位置形成一个坑；
2.定义两个指针left和right，left从左向右走，right从左向左走；
3.如果Key值位于数组最左边，需要right先走；如果Key值位于数组组右边，需要left先走；
4.在走的过程中，当end遇到小于Key的数，才停下，然后将right位置的值填放到坑位置，此时right位置处形成一个坑；然后begin开始走，直到遇到大于Key的数，然后将left位置的值填放到坑位置，此时left位置处形成一个坑；然后right再走，规则如上，直到left和right相遇，此时再将位于Key值填放到坑位置处；
5.此时，Key左边的值都是小于等于Key的数，Key右边的值都是大于等于Key的数；
6.然后再对Key左边的数以及Key右边的数分别进行如上操作，直到待排序列只有一个元素为止。
动画演示：
代码如下：
因为该方法包含大量的递归，当数据量较大时会发生栈溢出，因此做一些优化，包括【三数取中】和【当待排区间长度小于某个常数时，不再递归进行快排，而是使用直接插入排序】
public static void quickSort(int[] array){ quick(array,0,array.length-1); } private static void quick(int[] array,int start,int end){ if(start>=end) return; if(end-start<=7){ insertSortRange(array,start,end); return; } int pivot=partitionHole(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } private static void insertSortRange(int[] array,int begin,int end) { for (int i = begin+1; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= begin ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static int midOfThree(int[] array, int left, int right) { int mid = (left+right) / 2; if(array[left] < array[right]) { if(array[mid] < array[left]) { return left; }else if(array[mid] > array[right]) { return right; }else { return mid; } }else { if(array[mid] > array[left]) { return left; }else if(array[mid] < array[right]) { return right; }else { return mid; } } } private static int partitionHole(int[] array,int left,int right){ int key=array[left]; while(left<right){ while(left<right && array[right]>=key) right--; array[left]=array[right]; while(left<right && array[left]<=key) left++; array[right]=array[left]; } array[left]=key; return left; } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }时间复杂度：O(N*logN)
空间复杂度：O(1)
前后指针法
步骤：
1.选定数组最左边的值为基准值；
2.定义两个指针prev和cur，开始时prev在最左边，cur在prev的下一个位置；
3.让cur向右走，如果cur位置的值大于基准值，只需cur继续向右移动，直到遇到比基准值小的值；
4.如果cur位置的值小于基准值，先让prev向右移动一个位置，然后交换prev位置的值和cur位置的值，直到cur走到数组末尾。
代码如下：
因为该方法包含大量的递归，当数据量较大时会发生栈溢出，因此做一些优化，包括【三数取中】和【当待排区间长度小于某个常数时，不再递归进行快排，而是使用直接插入排序】
public static void quickSort(int[] array){ quick(array,0,array.length-1); } private static void quick(int[] array,int start,int end){ if(start>=end) return; if(end-start<=7){ insertSortRange(array,start,end); return; } int pivot=partitionDouble(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } private static void insertSortRange(int[] array,int begin,int end) { for (int i = begin+1; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= begin ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static int midOfThree(int[] array, int left, int right) { int mid = (left+right) / 2; if(array[left] < array[right]) { if(array[mid] < array[left]) { return left; }else if(array[mid] > array[right]) { return right; }else { return mid; } }else { if(array[mid] > array[left]) { return left; }else if(array[mid] < array[right]) { return right; }else { return mid; } } } private static int partitionDouble(int[] array,int left,int right){ int prev=left,cur=prev+1; while(cur<array.length){ if(array[cur]<array[left] && array[++prev]!=array[cur]) swap(array,prev,cur); cur++; } swap(array,prev,left); return prev; } private static void swap(int[] array,int i,int j){ int ret=array[i]; array[i]=array[j]; array[j]=ret; }时间复杂度：O(N*logN)
空间复杂度：O(1)
非递归版
代码如下：
public static void quickSortNor(int[] array) { Stack<Integer> stack = new Stack<>(); int left = 0; int right = array.length-1; int piovt = partitionHole(array,left,right); if(piovt - 1 > left) { stack.push(left); stack.push(piovt-1); } if(piovt + 1 < right) { stack.push(piovt+1); stack.push(right); } while (!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); piovt = partitionHole(array,left,right); if(piovt - 1 > left) { stack.push(left); stack.push(piovt-1); } if(piovt + 1 < right) { stack.push(piovt+1); stack.push(right); } } }归并排序
递归版
使用递归不断将区间二分，直到区间只有一个元素为止，然后将两个区间进行排序合并，直到将所有区间合并完。
代码如下：
public static void mergeSort(int[] array){ int[] dst=new int[array.length]; dst= Arrays.copyOf(array,array.length); merge(array,dst,0,array.length-1); for(int i=0;i<array.length;i++) array[i]=dst[i]; } private static void merge(int[] src,int[] dst,int start,int end){ if(start>=end) return; int mid=(start+end)>>1; merge(dst,src,start,mid); merge(dst,src,mid+1,end); int i=start,j=mid+1,k=start; while(i<=mid || j<=end){ if(j>end || (i<=mid && src[i]<src[j])) dst[k++]=src[i++]; else dst[k++]=src[j++]; } }时间复杂度：O(N*logN)
空间复杂度：O(N)
非递归版
将整个区间划分为长度为1,2,4,8，..........最大为N的小区间，然后对相邻的长度为1,2,4,8，..........最大为N的小区间分别进行排序合并，最终就排好序了。
代码如下：
public static void mergeSortNor(int[] array){ int[] src=array; int[] dst=new int[array.length]; for(int step=1;step<array.length;step+=step){ for(int start=0;start<array.length;start+=step*2){ int mid=Math.min(start+step-1,array.length-1); int end=Math.min(start+2*step-1,array.length-1); int i=start,j=mid+1,k=start; while(i<=mid || j<=end){ if(j>end || (i<=mid && src[i]<src[j])) dst[k++]=src[i++]; else dst[k++]=src[j++]; } } int[] tmp=src; src=dst; dst=tmp; } for(int i=0;i<array.length;i++) array[i]=src[i]; }时间复杂度：O(N*logN)
空间复杂度：O(N)
计数排序
先求出序列中的最大值maxVal和最小值minVal，然后开辟一个长度为maxVal-minVal+1的数组，值全都初始化为0，然后遍历整个数组，将下标为每个位置的值减去minVal处的值++，然后再重复将每个位置的值表示的次数次，将对应的值【下标+minVal】存放到原数组中。
动画演示：
代码如下：
public static void countSort(int[] array) { int minVal = array[0]; int maxVal = array[0]; for (int i = 1; i < array.length; i++) { if(array[i] < minVal) { minVal = array[i]; } if(array[i] > maxVal) { maxVal = array[i]; } } int[] count = new int[maxVal-minVal+1]; for (int i = 0; i < array.length; i++) { count[array[i]-minVal]++; } int index = 0; for (int i = 0; i < count.length; i++) { while (count[i] > 0) { array[index] = i+minVal; index++; count[i]--; } } }时间复杂度：O(N)
空间复杂度：O(N)
