1.排序的概念及引用
1.1 排序的概念
排序：就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：两个相等的数据，在排序前后其相对前后位置没有发生变化的排序就称之为稳定的排序。
1.2 常见的排序算法
2.插入排序
2.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 { break; } } //j下标的下一个位置就是tmp应该在的位置 array[j+1]=tmp; } }
特性总结：
1.元素集合越接近于有序，直接插入排序的时间效率越高（趋近于O（N）），因为内层循环直接break了。
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定
2.2 希尔排序（最小增量排序）
希尔排序其实是直接插入排序的优化，先通过将数据多次分组进行直接插入排序的预排序方式，使得元素集合尽可能趋于有序，最后再进行直接插入排序，将时间效率提高。
以下图具体操作为例：每次分组的间隔不好确定，以每次除以2为例，先进行分组预排序，最后进行直接插入排序。
代码实现：
public 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; } } public static void shellSort(int[] array) { //确定分组间隔，间隔不断减小进行预排序 int gap=array.length; while (gap>1) { shell(array,gap); gap/=2; } //再经过预排序后元素集合已经趋于有序，最后进行直接插入排序 shell(array,1); }
特性总结：
1.gap的确定方式影响时间复杂度，经统计得下结果
2.时间复杂度O(N^1.3 - N^1.5)
3.空间复杂度O(1)
4.稳定性：不稳定
3.选择排序
交换函数：
用于交换数组两个下标位置的元素，在后边的排序算法中可能多次用到该方法
public static void swap(int[] array,int i,int j) { int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
3.1 直接选择排序
从前往后每次从待排序列中选出最小元素，放在序列的起始位置，直到全部待排数据排完。
代码实现：
public static void selectSort(int[] array) { for (int i = 0; i < array.length-1; i++) { int minIndex=i;//记录待排序列的最小元素下标 for (int j = i+1; j <array.length ; j++) { if(array[j]<array[minIndex]) { minIndex=j; } } swap(array,minIndex,i); } }
特性总结：
- 时间复杂度O(N^2)
- 空间复杂度O(1)
- 稳定性：不稳定
优化：
在上边的代码实现中，每次遍历只是记录了最小元素的下标，如果想让时间效率更高，我们可以在一次遍历的过程中同时记录最大元素的下标和最小元素的下标，将最小元素放在待排序列的起始位置，将最大元素放在待排元素的结束位置。
代码实现：
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[minIndex]) { minIndex=i; } if(array[i]>array[maxIndex]) { maxIndex=i; } } swap(array,left,minIndex); //修正max的下标 if(left==maxIndex) { maxIndex=minIndex; } swap(array,right,maxIndex); left++; right--; } }
上边需要注意为什么要修正max下标，这是因为如果left位置元素就是最大元素，在进行第一个swap时，这个最大元素就被换到了minIndex的位置，所以需要修正下标，再完成第二个swap。
3.2 堆排序
以排升序为例，堆排序的具体操作如下：
- 建大堆
- 堆顶堆尾元素互换
- 向下调整堆顶元素，重复操作，直至完成所有元素的调整
代码实现：
先建大堆：
private static void createBigHeap(int[] array) { //先找到最后一棵子树的父结点，让每棵子树成为大顶堆 for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { shiftDown(array,parent,array.length); } } private static void shiftDown(int[] array,int parent, int len) { //保证有左孩子 int child=2*parent+1; while (child<len) { //如果有右孩子，左右孩子比较，child记录较大值的下标 if(child+1<len&&array[child]<array[child+1]) { child++; } if(array[child]>array[parent]) { swap(array,child,parent); //继续向下调整 parent=child; child=2*parent+1; }else { break; } } } private static void swap(int[] array,int i,int j) { int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
再做调整：
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--; } }
特性总结：
- 时间复杂度：O(N*og2N)
- 空间复杂度：O(1)
- 稳定性：稳定
4.交换排序
4.1 冒泡排序
从左往右遍历n-1趟，每次遍历，如果不符合左边小于右边，就交换两者位置，这样每次遍历都能把待排集合中的最大值放在最后。
代码实现：
public static void bubbleSort(int[] array) { //外层循环确定趟数 for (int i = 0; i < array.length-1; i++) { boolean flag=false; //内存循环调整元素，遍历后把最大元素放在最后，所以比较次数每次减1 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)
- 稳定性：稳定
4.2 快速排序
快排详情点击跳转【排序算法性能王——快速排序】
5.归并排序
思想：
其中心思想就是合并两个有序数组。先将序列拆解使得每个子序列有序，再二路归并使子序列段间有序，最后得到有序序列。
合并有序数组代码：
private static void merge(int[] array,int start,int end,int midIndex) { int[] tmpArr=new int[end-start+1];//开辟临时数组用于存储排好序的数组 int k=0; int s1=start;//两个区间段 int s2=midIndex+1; while (s1<=midIndex&&s2<=end) {//保证两个区间段都有数 if(array[s1]<=array[s2]) { tmpArr[k++]=array[s1++]; }else { tmpArr[k++]=array[s2++]; } } //当两个归并段中有一段没数据后，把另一段剩余数据全部拷贝到tmpArr数组中去 while (s1<=midIndex) { tmpArr[k++]=array[s1++]; } while (s2<=end) { tmpArr[k++]=array[s2++]; } //把排好序的数字拷贝回原数组 for (int i = 0; i < k; i++) { array[i+start]=tmpArr[i]; } }
实现代码：
递归下去把数组拆解开，回溯上来得到有序数组
public static void mergeSort(int[] array) { mergeSortFunc(array,0,array.length-1); } private static void mergeSortFunc(int[] array,int left,int right) { if(left>=right) { return; } int mid=(left+right)/2; //分解左边 mergeSortFunc(array,left,mid); //分解右边 mergeSortFunc(array,mid+1,right); //进行合并 merge(array,left,right,mid); }
每层都总共归并N个元素，共有log2N层，时间复杂度为O(N*log2N)
非递归实现：
非递归实现的思想就是多次分组进行归并，首先两个两个数据进行归并，然后四个四个归并，直到分组涵盖数据数大于数组长度停止。（难点是如何分组）
public static void mergeSort2(int[] array) { int gap=1;//每组元素个数 while (gap<array.length) { //一次遍历完成后，每组元素个数多一倍再次进行归并 for (int i = 0; i < array.length; i+=gap*2) { int s1=i; int e1=s1+gap-1; //下边的三个if条件都是为了防止空指针异常 if(e1>=array.length) { e1=array.length-1; } int s2=e1+1; if(s2>=array.length) { s2=array.length-1; } int e2=s2+gap-1; if(e2>=array.length) { e2=array.length-1; } merge(array,s1,e2,e1); } gap*=2; } }
特性总结：
- 时间复杂度：O(N*log2N)
- 空间复杂度：O(N)
- 稳定性：稳定
6.总结及性能分析
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(N^2) | O(1) | 稳定 |
| 希尔排序 | O(N^1.3~1.5) | O(1) | 不稳定 |
| 直接选择排序 | O(N^2) | O(1) | 不稳定 |
堆排序 |
O(N*log2N) | O(1) | 不稳定 |
| 冒泡排序 | O(N^2) | O(1) | 稳定 |
快速排序 |
O(N*log2N) | O(log2N) | 不稳定 |
归并排序 |
O(N*log2N) | O(N) |
稳定 |
