Arrays.sort

今天看看这个经常用的函数实现原理
基于jdk1.8

public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

我们就用这个为例子走一边流程：
我们可以看到其实sort它调用的是DualPivotQuicksort.sort这样一个静态方法。
这个类中，我们先看看有些常量：
* If the length of an array to be sorted is less than this
* constant, Quicksort is used in preference to merge sort.
*/
private static final int QUICKSORT_THRESHOLD = 286;

这个意思就是说在286以内的时候，arrays.sort排序是优先使用快排而不是归并排序

在sort中，
if (length < INSERTION_SORT_THRESHOLD)

如果length小于47 那么用直接插入排序
* 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;

或者是pair insertion sort

*   do {
                if (left >= right) {
                    return;
                }
            } while (a[++left] >= a[left - 1]);

            /*
             * Every element from adjoining part plays the role
             * of sentinel, therefore this allows us to avoid the
             * left range check on each iteration. Moreover, we use
             * the more optimized algorithm, so called pair insertion
             * sort, which is faster (in the context of Quicksort)
             * than traditional implementation of insertion sort.
             */
            for (int k = left; ++left <= right; k = ++left) {
                int a1 = a[k], a2 = a[left];

                if (a1 < a2) {
                    a2 = a1; a1 = a[left];
                }
                while (a1 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a1;

                while (a2 < a[--k]) {
                    a[k + 1] = a[k];
                }
                a[k + 1] = a2;
            }
            int last = a[right];

            while (last < a[--right]) {
                a[right + 1] = a[right];
            }
            a[right + 1] = last;

这个条件是用leftmore实现的，后面的是用于具有连续增长子序列的时候用的，用两个a1,a2分别表示遍历的两个相邻的数，保证a1大于a2，先找到a1应该所在的位置，在从a1位置向前找到a2的位置。
当然这一切必须保证数组长度为偶数，如果是奇数在对末尾的数进行排序。

如果大于47 则用改进过的快排。
首先将所有的数据段分为7段，
* int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;

如果这五个数大小都不同

a[e2] = a[left];
a[e4] = a[right];

        /*
         * Skip elements, which are less or greater than pivot values.
         */
        while (a[++less] < pivot1);
        while (a[--great] > pivot2);

        /*
         * Partitioning:
         *
         *   left part           center part                   right part
         * +--------------------------------------------------------------+
         * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
         * +--------------------------------------------------------------+
         *               ^                          ^       ^
         *               |                          |       |
         *              less                        k     great
         *
         * Invariants:
         *
         *              all in (left, less)   < pivot1
         *    pivot1 <= all in [less, k)     <= pivot2
         *              all in (great, right) > pivot2
         *
         * Pointer k is the first index of ?-part.
         */

正如图中所写的，它其实找到了小于pivot1的临界值和大于pivot2的临界值。
* outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
a[k] = a[less];
/*
* 这段代码是将比pivot1小的值移到左端
/
a[less] = ak;
++less;
} else if (ak > pivot2) { 移到到右端
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] < pivot1) { // a[great] <= pivot2
a[k] = a[less];
a[less] = a[great];
++less;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
/
* Here and below we use "a[i] = b; i--;" instead
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
--great;
}
}

将整个数据段分为小于pivot1 大于pivot2 以及两个之间的三个数据段

*       sort(a, left, less - 2, leftmost);
        sort(a, great + 2, right, false);

将第一和第三数据段排序，接着在第二段中分成等于pivot1 等于pivot2以及其他的，
再对中间的进行排序。这么一来，这种可能就排序完了。

还有一种如果五个值有相同的话，用e3作为分界线。
这个和上面的是差不多的，只是分成大于pivot 等于pivot 和小于pivot
再递归排序就好了

以上是小于286 大于286的时候用来另一种方法。

int[] run = new int[MAX_RUN_COUNT + 1];

代码中用了这个数字去衡量这个排序的数组是否具有局部有序性。

if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}

无序的情况下直接有快排就行了。
如果有序的情况下直接用归并排序。

读源码，是我们了解大神领域的一大捷径
生命不息，奋斗不止