解析JDK8中Arrays.sort底层原理及其排序算法的选择

2019-12-11

字数统计: 1.5k字 | 阅读时长≈ 6分

暂时网上看过很多JDK8中Arrays.sort的底层原理，有些说是插入排序，有些说是归并排序，也有说大于域值用计数排序法，否则就使用插入排序。。。其实不全对。让我们对着源码分析个究竟：

 // Use Quicksort on small arrays
 if (right - left < QUICKSORT_THRESHOLD) {//QUICKSORT_THRESHOLD = 286
    sort(a, left, right, true);
    return;
}

数组一进来，会碰到第一个阀值QUICKSORT_THRESHOLD（286），注解上说，小过这个阀值的进入Quicksort （快速排序），其实并不全是，点进去sort(a, left, right, true);方法能看见：

1
2
3

// Use insertion sort on tiny arrays
       if (length < INSERTION_SORT_THRESHOLD) {//INSERTION_SORT_THRESHOLD=47
           if (leftmost) ……

我们看到第二个阀值INSERTION_SORT_THRESHOLD（47），如果元素少于47这个阀值，就用插入排序，往下看确实如此：

/*
            * Traditional (without sentinel) insertion sort,
            * optimized for server VM, is used in case of
            * the leftmost part.
            */
           for (int i = left, j = i; i < right; j = ++i) {
               int ai = a[i + 1];
               while (ai < a[j]) {
                   a[j + 1] = a[j];
                   if (j-- == left) {
                       break;
                   }
               }
               a[j + 1] = ai;
           }

插入排序动图演示：
在这里插入图片描述
元素少于47用插入排序

至于大过INSERTION_SORT_THRESHOLD（47）的，用一种快速排序的方法：
1.从数列中挑出五个元素，称为 “基准”（pivot）；
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序动图演示：
在这里插入图片描述

这是少于阀值QUICKSORT_THRESHOLD（286）的两种情况，至于大于286的，它会进入归并排序（Merge Sort），但在此之前，它有个小动作：

// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
    if (a[k] < a[k + 1]) { // ascending
        while (++k <= right && a[k - 1] <= a[k]);
    } else if (a[k] > a[k + 1]) { // descending
        while (++k <= right && a[k - 1] >= a[k]);
        for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
            int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
        }
    } else { // equal
        for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
            if (--m == 0) {
                sort(a, left, right, true);
                return;
            }
        }
    }

    /*
     * The array is not highly structured,
     * use Quicksort instead of merge sort.
     */
    if (++count == MAX_RUN_COUNT) {
        sort(a, left, right, true);
        return;
    }
}

这里主要作用是看他数组具不具备结构：实际逻辑是分组排序，每降序为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后最后的8后面继续往后面找。。。

每遇到这样一个降序组，++count，当count大于MAX_RUN_COUNT（67），被判断为这个数组不具备结构（也就是这数据时而升时而降），然后送给之前的sort(里面的快速排序)的方法（The array is not highly structured,use Quicksort instead of merge sort.）。

如果count少于MAX_RUN_COUNT（67）的，说明这个数组还有点结构，就继续往下走下面的归并排序：

1
2
3

// Determine alternation base for merge
byte odd = 0;    
for (int n = 1; (n <<= 1) < count;odd ^= 1);

从这里开始，正式进入归并排序（Merge Sort）！

// Merging
for (int last; count > 1; count = last) {
    for (int k = (last = 0) + 2; k <= count; k += 2) {
        int hi = run[k], mi = run[k - 1];
        for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
            if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                b[i + bo] = a[p++ + ao];
            } else {
                b[i + bo] = a[q++ + ao];
            }
        }
        run[++last] = hi;
    }
    if ((count & 1) != 0) {
        for (int i = right, lo = run[count - 1]; --i >= lo;
            b[i + bo] = a[i + ao]
        );
        run[++last] = right;
    }
    int[] t = a; a = b; b = t;
    int o = ao; ao = bo; bo = o;
}

归并排序动图演示：
在这里插入图片描述
总结：
从上面分析，Arrays.sort并不是单一的排序，而是插入排序，快速排序，归并排序三种排序的组合，为此我画了个流程图：

算法的选择：

PS：关于排序算法的文章，推荐这两篇，个人觉得写得挺好，容易入门：
https://mp.weixin.qq.com/s/t0dsJeN397wO41pwBWPeTg
https://www.cnblogs.com/huangbw/p/7398418.html

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

时间复杂度按n越大算法越复杂来排的话：常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n²)、立方阶O(n³)、……k次方阶O(n的k次方)、指数阶O(2的n次方)。

O(nlogn)只代表增长量级，同一个量级前面的常数也可以不一样，不同数量下面的实际运算时间也可以不一样。数量非常小的情况下（就像上面说到的，少于47的），插入排序等可能会比快速排序更快。
所以数组少于47的会进入插入排序。

快排数据越无序越快（加入随机化后基本不会退化），平均常数最小，不需要额外空间，不稳定排序。
归排速度稳定，常数比快排略大，需要额外空间，稳定排序。
所以大于或等于47或少于286会进入快排，而在大于或等于286后，会有个小动作：“// Check if the array is nearly sorted”。
这里第一个作用是先梳理一下数据方便后续的归并排序，第二个作用就是即便大于286，但在降序组太多的时候（被判断为没有结构的数据，The array is not highly structured,use Quicksort instead of merge sort.），要转回快速排序。

这就是jdk8中Arrays.sort的底层原理，自己在研究和分析中学到很多，希望能给各位工作中或面试中一些启发和帮助！Thanks for watching！

本文作者： 生活,生活?
本文链接： ayjcsgm.github.io/2019/12/11/解析JDK8中Arrays-sort底层原理及其排序算法的选择/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！