一、排序的该您及引用
1.1 排序的概念
排序：所谓排序，就是一串纪录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部存放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动的数据的排序。
1.2 常见的排序算法
二、常见的排序算法的实现
2.1 插入排序
2.1.1 基本思想
其基本思想就是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
2.1.2 直接插入排序
当插入第i(i>=1)个元素时，前面的arr[0],arr[1],.....,arr[i-1]已经排好序，此时用arr[i]的排序码与array[i-1],array[i-2],...的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
public static void insertSort(int []array){ int j; for (int i = 1; i < array.length; i++) { int tmp=array[i]; for (j = i-1; j >=0 ; j--) { if(array[j]>tmp){ array[j+1]=array[j]; }else { break; } } array[j+1]=tmp; } }
直接插入排序的特性总结：
1.元素集合越接近有序，直接插入的排序算法时间效率越高
2.时间复杂度：O（N^2）
3.空间复杂度：O(1)
4.稳定性：稳定
2.1.3 希尔排序（缩小增量排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为 的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达组数=1时，所有记录在统一组内排好序。
public static void shellSort(int []array){ //gap分为多少组 int gap=array.length; while (gap>1){ shell(array,gap); gap/=2; } shell(array,1); } public static void shell(int []array,int gap){ //i是每组的第二个数据开始来比较 for (int i = gap; i < array.length; i++) { int tmp=array[i]; int j=i-gap; for (;j>=0;j-=gap){ if(tmp<array[j]){ array[j+gap]=array[j]; }else { break; } } array[j+gap]=tmp; } }
希尔排序的 特性总结：
1.希尔排序是对直接插入排序的优化。
2.当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定:O(N^1.3)~O(N^1.5)
4.稳定性：不稳定
2.2选择排序
2.2.1 基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
2.2.2 直接选择排序：
1.在元素集合array[i]--array[n-1]中选择关键码最大的数据元素
2.若它不是这组元素的最后一个（或第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换
3.在剩余的array[i]--array[n-2](array[i+1]--array[n-1]集合中，重复上述步骤，直到集合剩余一个元素。
public static void selectSort1(int []array){ for (int i=0;i<array.length;i++){ for (int j = i+1; j <array.length ; j++) { if(array[i]>array[j]){ swap(array,i,j); } } } } public static void selectSort2(int []array){ int 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[maxIndex]){ maxIndex=i; } if(array[i]<array[minIndex]){ minIndex=i; } } swap(array,left,minIndex); //若maxIndex恰巧为left，最大值会被换走 if(maxIndex==left){ maxIndex=minIndex; } swap(array,right,maxIndex); left++; right--; } } public static void swap(int []array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
【直接选择排序的特性总结】
1.直接选择排序思考非常好理解，但是效率不高，实际很少使用
2.时间复杂度O(N^2)
3.空间复杂度O(1)
4.稳定性：不稳定
2.2.3堆排序
堆排序是指利用堆积树这种结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据，需要注意的是排升序，建大堆，排降序，建小堆。
public static void heapSort(int []array){ creatBigHeap(array); int end=array.length-1; while (end>0){ swap(array,0,end); shiftDown(array,0,end); end--; } } public static void creatBigHeap(int []array){ for (int i = (array.length-1-1)/2;i >=0; i--) { shiftDown(array,i,array.length); } } public static void shiftDown(int []array,int parent,int lenth){ int child=parent*2+1; while (child<lenth){ if(parent*2+2<lenth){ child=array[child]>array[child+1]?child:child+1; } if(array[parent]<array[child]){ swap(array,parent,child); parent=child; child=parent*2+1; }else { break; } } } public static void swap(int []array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
【总结】
1.堆排序使用堆来选数，效率就高了很多
2.时间复杂度：O(N*logN)
3.空间复杂度：O(1)
4.稳定性：不稳定
2.3 交换排序
基本思想：所谓交换，就是根据序列中两个纪录键值的比较结果来对换这两个纪录在序列中的位置，交换排序的特点是：将键值较大的纪录向序列的尾部移动，键值较小的纪录向序列的前部移动。
2.3.1 冒泡排序
public static void bubleSort(int []array){ for (int i = 0; i < array.length; i++) { for (int j = 0; j <array.length-1-i; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); } } } } public static void swap(int []array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
【冒泡排序的特性总结】
1.冒泡排序是一种非常容易理解的排序
2.时间复杂度：O(N^2)
3.空间复杂度:O(1)
4.稳定性：稳定
2.3.2 快速排序
基本思想：任取待排元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，知道所有元素都排列在相应位置上为止。
public static int partition2(int []array,int left,int right){ int init=left; int tmp=array[left]; while (left<right){ while (array[right]>=tmp&&left<right){ right--; } while (array[left]<=tmp&&left<right){ left++; } swap(array,left,right); } swap(array,left,init); return left; } //挖空法 public static int partition(int []array,int left,int right){ int tmp=array[left]; while (left<right){ while (array[right]>=tmp&&left<right){ right--; } array[left]=array[right]; while (array[left]<=tmp&&left<right){ left++; } array[right]=array[left]; } array[left]=tmp; if(left==right) return left; return -1; } //双指针法 public static int partition3(int []array,int left,int right){ int prev=left; int cur=left+1; while (cur<=right){ /* if(array[cur]>=array[left]){ cur++; }else { prev++; swap(array,prev,cur); cur++; }*/ if (array[cur] < array[left] && array[++prev]!=array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,left); return prev; }
快速排序优化
1.三数取中法选key
2.递归到小的子区间，可以考虑使用插入排序
public static void quick(int []array,int left,int right){ if(left>=right) return; //将中间值放在left位置作为基准 threeNode(array,left,right); //快排结构类似与完全二叉树，当排到最后两行时，元素较多且趋于有序，使用插入排序效率更高，且能够降低递归次数过多导致栈溢出的风险 if(right-left<14){ insertSort(array); return; } //int pivot=partition(array,left,right); //int pivot=partition2(array,left,right); int pivot=partition3(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); } //三数取中 public static void threeNode(int []array,int left,int right){ int mid=(left+right)/2; if(array[left]>array[right]){ if(array[mid]<array[right]){ swap(array,left,right); }else if(array[mid]>array[left]){ }else { swap(array,left,mid); } }else { //array[left]<array[right] if(array[mid]<array[left]){ }else if(array[mid]>array[right]){ swap(array, left, right); }else { swap(array,left,mid); } } }
非递归实现快速排序
void quickSortNonR(int[] a, int left, int right) { Stack<Integer> st = new Stack<>(); st.push(left); st.push(right); while (!st.empty()) { right = st.pop(); left = st.pop(); if(right - left <= 0) continue; int div = PartSort1(a, left, right); // 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right) st.push(div+1); st.push(right); st.push(left); st.push(div); } }
快速排序总结
1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢交快速排序
2.时间复杂度：O(N*logN)
3.空间复杂度：O(logN)
4.稳定性：不稳定
2.4 归并排序
2.4.1基本思想
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤： 
public static void mergeSort(int []array){ merge(array,0,array.length-1); } public static void merge(int []array,int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; merge(array,left,mid); merge(array,mid+1,right); mergefunc(array,left,mid,right); } public static void mergefunc(int []array,int left,int mid,int right){ int []tmp=new int[right-left+1]; int k=0; int s1=left; int s2=mid+1; while (s1<=mid&&s2<=right){ if(array[s1]<array[s2]){ tmp[k++]=array[s1++]; }else { tmp[k++]=array[s2++]; } } while (s1<=mid){ tmp[k++]=array[s1++]; } while (s2<=right){ tmp[k++]=array[s2++]; } //在原数组中对应的下标范围为left~right for (int i = 0; i <tmp.length; i++) { array[i+left]=tmp[i]; } } //非递归排序 public static void mergeSort2(int []array){ //gap每组元素的个数,从一开始是因为每组一个元素必定是有序的 int gap=1; while (gap<array.length){ for (int i=0;i<array.length;i+=gap*2){ int left=i; //由于元素不一定能够被均分，存在数组越界的情况 int mid=i+gap-1; if(mid>array.length-1){ mid=array.length-1; } int right=i+2*gap-1; if(right>array.length-1){ right=array.length-1; } mergefunc(array,i,mid,right); } gap*=2; } }
归并排序总结：
1.归并排序的缺点在于需要O(N)的空间复杂度，归并排序的思考更多是解决在磁盘中的外排问题。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(N)
4.稳定性：稳定
三、排序的算法复杂度及稳定性分析
四、其他非基于比较排序
4.1计数排序
public static void countSort(int []array){ int max=array[0]; int min=array[0]; for (int i = 0; i < array.length; i++) { if(array[i]<min){ min=array[i]; } if(array[i]>max){ max=array[i]; } } int []brr=new int[max-min+1]; //遍历数组，在计数数组当中，纪录每个数字出现的次数 for (int i = 0; i < array.length; i++) { brr[array[i]-min]++; } int index=0; for (int i = 0; i <brr.length; i++) { int n=brr[i]; while (n>0){ n--; array[index++]=i+min; } } System.out.println(Arrays.toString(array)); }
总结：
1.计数排序在数据范围集中时，效率很高，但是适用范围以及场景有限
2.时间复杂度：O(Max(n,最大值-最小值的范围））
3.时间复杂度：O(范围)
