常见的排序算法：
按照插入排序分：1.直接插入排序 2.希尔排序
按照选择排序分：1.选择排序 2.堆排序
按照交换排序分：1.冒泡排序 2.快速排序
按照归并排序分：1.归并排序
常见的排序思想：是使用双指针或者三指针，在同一个数组上遍历、比较、交换。
1、直接插入排序
类比于扑克牌抽排，双指针思路。
1.时间复杂度：最坏情况下O(N^2)，如54321，最好情况下O(N)，如12345（只用i动，j不用走）
2.空间复杂度：O(1)
3.稳定性：稳定
4.使用场景：元素集合越接近有序，直接插入排序算法时间效率越高。
public void insertSort(int[] array){
//[27,15,9,18,28]
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i-1;
for (; j >=0 ; j--) {
if (array[j] > temp){
array[j+1] = array[j];
}else {
//如果不用调整，则表示已经找到了该放的位置了
//因为前面都有序了
break;
}
}
//当j循环走完以后，要么就是走完了所有，要么就是找到了最小位置
//所以走完以后直接把j+1的位置赋值为temp即可
array[j+1] = temp;
}
}
2、希尔排序（缩小增量排序）
基本思想：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。当到达 =1时，所有记录在统一组内排好序。
时间复杂度：O(n^1.25)~O(1.6*n^1.25)
空间复杂度：O(1)
稳定性：不稳定
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
跳着分的目的是让交换之后，大的数都在后面，小的数都在前面。前面的这些趟都是预排序，最后1趟才是真正的排序。每一组都是插入排序，越有序越快。
public void shellSort(int[] array){
int gap = array.length;
//gap表示array数组，分为多少个组
while (gap > 1){
//每次缩短一半的分组
gap /= 2;
shell(array,gap);
}
}
/**
* 对每组进行插入排序
* @param array
* @param gap
*/
public 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;
}
}
3、选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
public void selectSort(int[] array){
//双指针思想
for (int i = 0; i < array.length; i++) {
int miniIndex = i;
for (int j = i+1; j < array.length; j++) {
//如果j指向的数值小于最小值，那么就更新最小值索引
if (array[j] <= array[miniIndex]){
miniIndex = j;
}
}
//找到最小值索引以后，就跟i位置交换
swap(array,i,miniIndex);
}
}
//3指针思想
public void doubleSelectSort(int[] array){
int left = 0;
int right = array.length-1;
while (left < right){
int minIndex = left;
int maxIndex = left;
//走一趟left和right之间的值
for (int i = left + 1;i<= right;i++){
if (array[i] < array[minIndex]){
minIndex = i;
}
if (array[i] > array[maxIndex]){
maxIndex = i;
}
}
//注意，如果最大值在第一个位置，会出现bug
//如果最大值在下标为0的位置，此时第一个swap会把最大值换到minIndex位置上
//而第二个swap会把0位置的最小值换到数组最后一个位置，就乱了
swap(array,minIndex,left);
//如果最大值的索引，正好等于left
//交换完成以后，left存储的是最小值，minIndex存储的是最大值
//所以需要多加一步，将minIndex赋给maxIndex
if (maxIndex == left){
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
4、堆排序
利用堆的特性来排序。排升序是用大根堆，排降序是用小根堆。其实就是不断地将堆中的树进行向上升序或者向下排序，由于堆中的元素是大根堆或者小根堆排列的，所以最终的树就是有序的了。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
public void heapSort(int[] array){
//先把数组创建成堆
createHeap(array);
//从最后一棵树开始排序
int end = array.length-1;
while (end > 0){
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private void siftDown(int[] array,int parent, int lenght) {
int child = 2 * parent + 1;
while (child < lenght){
if (child + 1 child++; } if (array[child] > array[parent]){ swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } } private void createHeap(int[] array) { //从最后一个父亲结点开始创建 for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) { siftDown(array,parent,array.length); } } 5、冒泡排序 双指针 时间复杂度：O(n^2)，优化以后最好情况下可以达到O(n) 空间复杂度：O(1) 稳定性：稳定 public void bubbleSort(int[] array){ for (int i = 0; i < array.length-1; i++) { boolean flg = false; for (int j = 0; j < array.length-1-i; j++) { if (array[i] > array[j]){ swap(array,i,j); flg = true; } } if (!flg){ break; } } } 6、快速排序 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。 时间复杂度：最好的情况下，O(N*logN)，当最坏的情况下，O(N^2)，逆序或者有序 空间复杂度：O(logN) 稳定性：不稳定 上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。 其实最核心的任务就是找到相交点，交换。 6.1 Hoare法 递归以后层数多了可能会栈溢出。因为怕就怕他切分的这棵树，左边长右边短，或者左边短右边长。如果是均匀切分的话，其实是效果比较好的。 private 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 int partitionHoare(int[] array, int left, int right) { //待比较元素 int tmp = array[left]; int i =left; while (left < right){ //单独的循环，不能一直减到超过左边的边界 while (left < right && array[right] >= tmp){ right--; } while (left < right && array[left] <= tmp){ left ++; } //交换left和right找到的值 swap(array,left,right); } //此时left和right都在相遇点了，将相遇点换到最前面 swap(array,i,left); return left; } 6.2 挖坑法（Hoare衍生出来的） 挖坑法就是把基准从数组中拿出来，数组中就留下了一个坑，然后同样从右边和左边遍历，遇到大于或者小于基准的就把那个元素，拿到坑这个位置放下，反复循环，知道左右索引相遇，就把基准填入最后一个坑里。 private int partitionHole(int[] array,int left,int right){ //待比较元素 int tmp = array[left]; while (left < right){ //单独的循环，不能一直减到超过左边的边界 while (left < right && array[right] >= tmp){ right--; } //right找到比基准小的值，就把right所指向的元素填入left位置 //因为此时left位置就是坑 array[left] = array[right]; while (left < right && array[left] <= tmp){ left ++; } array[right] = array[left]; } array[left] = tmp; return left; } 值得注意的2个细节： 1，array[right] >= tmp 为什么要加等于？ 如果不加等于，会死循环。因为left=right，left无法++right无法--，会不停地交换这两个值。 2，为什么从右边开始而不是先从左边开始？ 如果先让left先走，那么走到相遇地方的时候，left指向的是一个比较大的数，此时将left和最左边交换，会让这个大的数换到最左边去。而如果是从右边先开始的话，right不断--，当遇到left的时候，right走到的是一个较小的数，此时再与最左边交换，就没问题。 6.3 前后指针法 cur用来指向比基准小的数，prev用来推着比基准大的数，cur不停地找比基准小的数，去和prev指向的比基准大的数交换。给人的感觉就是prev在不停地推着这些比基准大的数往前滚动，cur作为开路先锋去找小的数来交换。 //前后指针法1 private int partitionBFPoint1(int[] array, int left, int right) { int prev = left ; int cur = left+1; while (cur <= right) { if(array[cur] < array[left] && array[++prev] != array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,left); return prev; } //前后指针法2 private int partitionBFPoint2(int[] array, int left, int right) { int d = left + 1; int pivot = array[left]; for (int i = left + 1; i <= right; i++) { if (array[i] < pivot) { swap(array, i, d); d++; } } swap(array, d - 1, left); return d - 1; } 6.4 快速排序小结 三种快速排序的方法： 1.Hoare法 2.挖坑法 3.前后指针法 这三种方法每次划分以后的序列顺序，有可能是不一样的。 当面临一个序列，要你判断他用的哪一种快速排序的方法的时候。根据以往的经验，先后检验的顺序是挖坑法、Hoare法、前后指针法。