JDK排序

Collections.sort List的sort 内部会都会将链表转成数组，调用Arrays.sort

我们来看看JDK内置的排序算法是如何实现的

Arrays.sort内部逻辑

基本类型：

数据量少 -- 插入排序

数据量适中 -- 快速排序

海量数据 -- 根据无序程度来判定继续使用哪种算法

基本无序 -- 快速排序

基本有序 -- 归并排序

Object类型：

少量数据 -- 插入排序

大量数据 -- 归并排序

那么jdk是基于什么原理在不同场景下选择不同排序算法呢？

冒泡和选择直接忽略，插入在数据少或基本有序时有巨大效率优势，比快速和归并更快，快速和归并递归方法出栈入栈挺耗时

另外当大数据量基本有序时，归并更好，想象极端情况就是有序了，快排比较次数还是N+M，归并则只需要比较N次即可，后面M无脑循环录入即可

即使普通情况下，归并比较次数也通常比快排少很多，因为快排次数永远是length，而归并只需要前期两部分遍历比较，所以对于对象比较耗时时，选用归并

堆排序适用少量场景(大数据量TopK 比快排更省内存)，它是跳跃访问，对缓存不友好

选择排序算法，要基于数据量，是否要求稳定，有序程度，内存空间，排序内容综合考虑

1 冒泡排序

public class PopSort {  public static void sort(int[] arrays) {    //若上一次没有冒泡说明前缀已经有序，可直接退出    boolean flag = false;    //第一层控制总冒泡次数，为length-1次    for (int i = 0 ; i < arrays.length -1 ; i++) {      if (flag){        return;      }      flag = true;      //第二层控制每次冒泡的区间      for (int j = 1; j < arrays.length - i; j ++) {        if (arrays[j-1] > arrays[j] ) {          //有任意一次冒泡，则置为false代表下次还要继续          flag = false;          int tmp = arrays[j-1];          arrays[j-1] = arrays[j];          arrays[j] = tmp;        }      }    }  }  public static void main(String[] args) {    int[] arg = new int[]{4, 1, 8, 23, 100, 43, 6};    sort(arg);    System.out.println(NewJsonUtils.toJson(arg));  }}

2 选择排序

public class SelectSort {  public static void sort(int[] arrays) {    for (int i = 0; i < arrays.length - 1; i++) {      int maxIndex = 0;      int j;      for (j = 1; j < arrays.length - i; j++) {        if (arrays[j] > arrays[maxIndex]) {          maxIndex = j;        }      }      //上面循环结束的j需要--，才是最后索引      if (j - 1 != maxIndex) {        int tmp = arrays[j - 1];        arrays[j - 1] = arrays[maxIndex];        arrays[maxIndex] = tmp;      }    }  }  public static void main(String[] args) {    int[] arg = new int[]{4, 1, -8, 23, 100, 43, 6};    sort(arg);    System.out.println(NewJsonUtils.toJson(arg));  }}

3 插入排序

public class InsertSort {  public static void sort(int[] arrays) {    for (int i = 1; i < arrays.length; i++) {      int temp = arrays[i];      int j = i;      while (j - 1 >= 0) {        if (temp < arrays[j - 1]) {          arrays[j] = arrays[j - 1];          j = j - 1;        } else {          break;        }      }      arrays[j] = temp;    }  }  public static void main(String[] args) {    int[] arg = new int[]{4, 1, 8, 23, 100, 43, 6};    sort(arg);    System.out.println(NewJsonUtils.toJson(arg));  }}

4 希尔排序

直接插入基本有序的和元素较少时效率很的，就比如我们经常用的 Arrays.sort (),当元素个数少于 47 时，使用的排序算法就是直接插入排序。

那么直接希尔排序和直接插入排序有什么关系呢？

希尔排序是插入排序的一种，其思想简单点说就是有跨度的插入排序，这个跨度会逐渐变小，直到变为 1，变为 1 时记录也就基本有序

时间复杂度跟增量序列的选择有关，范围为 O(n^(1.3-2)) 在此之前的排序算法时间复杂度基本都是 O(n^2),希尔排序是突破这个时间复杂度的第一批算法之一

public class ShellSort {  public static void sort(int[] arrays) {    for (int n = arrays.length >> 1; n >= 1; n = n >> 1) {      for (int i = n; i < arrays.length; i++) {        int temp = arrays[i];        int j = i;        while (j - n >= 0) {          if (temp < arrays[j - n]) {            arrays[j] = arrays[j - n];            j = j - n;          } else {            break;          }        }        arrays[j] = temp;      }    }  }  public static void main(String[] args) {    int[] arg = new int[]{4, 1, 8, 23, -2, 43, 6};    sort(arg);    System.out.println(NewJsonUtils.toJson(arg));  }}

5 快速排序每次递归以start的值作为基准开启循环while(left<right)判断从右边向前同基准比较，当right<index时将right值替换到index处，重新设置index为right从左边向后同基准比较，当left>index时将left值替换到index处，重新设置index为left直到left和right相遇，此时array[left]=基准值，此时基准左边和右边全部满足小于 大于基准的要求继续对左半部分和右半部分排序

最好情况是每次基准都落在中间位置，此时是O(logN)

最差情况是每次基准都落在某一边，此时是O(N2)

public class QuitSort {    private static void sort(int[] array, int start, int end) {        if (start >= end) {            return;        }        int middleVal = array[start];        int left = start;        int right = end;        int tmpIndex = start;        while (left < right) {            while (left < right && array[right] >= middleVal) {                right--;            }            if (left < right) {                array[tmpIndex] = array[right];                tmpIndex = right;            }            while (left < right && array[left] <= middleVal) {                left++;            }            if (left < right) {                array[tmpIndex] = array[left];                tmpIndex = left;            }        }        array[left] = middleVal;        sort(array, start, left - 1);        sort(array, left + 1, end);    }    public static void main(String[] args) {        int[] arg = new int[]{4, 1, 8, 23, 6};        sort(arg, 0, arg.length - 1);        System.out.println(NewJsonUtils.toJson(arg));    }}

6 归并排序

因为都是从前向后遍历，即适用数组也可以用在链表上

public class MergeSort {    private static void sort(int[] array, int start, int end) {        if (start >= end) {            return;        }        int middle = (start + end) / 2;        sort(array, start, middle);        sort(array, middle + 1, end);        merge(array, start, middle, end);    }    private static void merge(int[] array, int start, int middle, int end) {        int[] res = new int[end - start + 1];        int i = 0;        int left = start;        int right = middle + 1;        while (left <= middle && right <= end) {            if (array[left] < array[right]) {                res[i++] = array[left++];            } else {                res[i++] = array[right++];            }        }        while (left <= middle) {            res[i++] = array[left++];        }        while (right <= end) {            res[i++] = array[right++];        }        for (int index = 0; index <= res.length - 1; index++) {            array[start + index] = res[index];        }    }    public static void main(String[] args) {        int[] arg = new int[]{4, 1, 8, 23, 6};        sort(arg, 0, arg.length - 1);        System.out.println(NewJsonUtils.toJson(arg));    }}

7 堆排序

基于二叉堆 (完全二叉树 && 每个节点大于等于（或小于等于）子树节点值)

1 将无序数组变成堆有两种不同的操作完成： 上浮 or 下沉

两种方式效率不一样： “下沉”需要遍历的节点数比“上浮”需要遍历的节点数少了一半，因为他只关心非叶子节点，所以此种情况选择下沉

2 堆某个节点有序化：假设是大顶堆

某节点变得比父节点更大或在堆底加入一个新元素，需要由下至上恢复堆顺序

某节点优先级下降（如将根节点替换为一个较小的元素），需要由上至下恢复堆顺序

堆排序分为两个阶段：1.将无序数组构造成堆 2. 不断将堆顶和尾部替换，缩小堆大小，将新顶部元素下沉获取新的堆顶

在操作堆时最好是将下标定义为从1开始，这样计算公式更加简洁

比如最后一个非叶子节length/2 、 父节点 index/2 、 左子 index*2 、右子 index*2+1

public class HeapSort {  public static void sort(int[] arrays) {    //构建索引初始为1的数组，方便下面计算    int[] nums = new int[arrays.length + 1];    int i = 1;    for (int num : arrays) {      nums[i++] = num;    }    //下沉建堆,从第一个非叶子节点，轮训直到顶端，结束后此时数组为大顶堆    for (int start = nums.length >> 1; start >= 1; start--) {      //注意这里填写的end，是原声数组长度，正好对标nums最后一个索引      down(nums, start, arrays.length);    }    //不断切断大顶堆顶部和尾部，重新下沉    int l = arrays.length;    while (l > 1) {      int temp = nums[1];      nums[1] = nums[l];      nums[l] = temp;      l--;      down(nums, 1, l);    }    for (int index = 1, s = 0; index < nums.length; ) {      arrays[s++] = nums[index++];    }  }  public static void down(int[] array, int start, int end) {    while (start << 1 <= end) {      int index = start << 1;      //当左右子节点都有，才比较两者大小，选其大      if (index + 1 <= end && array[index + 1] > array[index]) {        index++;      }      //当父节点非最大，则同最大子节点交换      if (array[start] < array[index]) {        int temp = array[start];        array[start] = array[index];        array[index] = temp;        start = index;      } else {        break;      }    }  }  public static void main(String[] args) {    int[] arg = new int[]{4, 1, 8, 23, 100, 43, 6};    sort(arg);    System.out.println(NewJsonUtils.toJson(arg));  }}

从时间和空间复杂度 堆排序非常好 ，但是呢它有两个缺点：

1 在数据变化频繁时维护堆的成本非层高昂

2 数据是跳跃访问，不能很好的利用数据空间局部性

快排虽然有理论最差O(N2)的缺点，但是可以优化随机算法避免

七大交换排序比较

快速排序最好情况是每次基准都在中点，此时递归次数为logN，每次递归总体比较N次，所以时间复杂度是NlogN，空间复杂度是logN(每次递归的占用空间)

最差情况基准每次都在某一侧，此时递归树退化为链表，递归次数为N，时间和空间变为N*N、N

可以通过随机法或者三数取中避免最差情况发生

归并排序 每次都是取中点分发数据递归，每次递归需要N个计算(合并)，空间上是额外数组N和递归调用logN

时间复杂度是NlogN，空间是N(忽略logN)

为什么大部分情况选择快排而不是归并呢？

一方面归并所需额外空间不容忽视：N+logN 快排是logN ，而且虽然时间复杂度看起来都是NlogN

但是归并每次都要遍历一遍数据赋值临时数组，最后再回填，相比快排一次遍历效率肯定差很多

不过他仍旧是快排的有力竟者者，当需要稳定排序或是当数据有序性很高时，

当数据有序性很高时，它的比较次数会少很多(极端情况本身有序时 比较次数是A N=A+B)，而快排比较次数永远是N

JDK的排序当对象或大数据量整体有序选择归并

堆排序为何如此默默无闻？

时间复杂度O(N+NlogN) 空间是O(1) 不稳定 看似差别不大，但是它算法内每次取数的成本其实远远大于快速和归并

因为其每次都是跳跃访问，这样局部性缓存无法发挥效率，其只在特殊场景下有应用topK

选择、冒泡、插入，时间复杂度都是n*n，但是数据量少时JDK选择用插入，为啥？

冒泡每次比较完都要交换，交换一次相当于三次复制，很蠢

选择属于无脑性迭代，每次完毕也是一次交换(三次复制)

而插入当数据有序性高时可以提前结束，且每次比较完都是一次复制即可

所谓N*N只是理论上问题解决成本的趋势，每次N的计算成本和常量、低阶也都是不可忽视的