Arrays.sort使用的什么排序?

发表于 | 分类于 |
字数统计: 2.1k | 阅读时长 ≈ 9

[TOC]

  • 双轴快排(DualPivotQuicksort)，顾名思义有两个轴元素pivot1，pivot2，且pivot ≤
    pivot2，将序列分成三段：x < pivot1、pivot1 ≤ x ≤ pivot2、x >pivot2，然后分别对三段进行递归。这个算法通常会比传统的快排效率更高，也因此被作为Arrays.java中给基本类型的数据排序的具体实现。

下面我们以JDK1.8中Arrays对int型数组的排序为例来介绍其中使用的双轴快排：

1.判断数组的长度是否大于286，大于则使用归并排序(merge sort)，否则执行2。

1
2
3
4
5
6
7
// Use Quicksort on small arrays
   if (right - left < QUICKSORT_THRESHOLD) {
           sort(a, left, right, true);
           return;
   }
   // Merge sort
   ......

2.判断数组长度是否小于47，小于则直接采用插入排序(insertion sort)，否则执行3。

1
2
3
4
5
// Use insertion sort on tiny arrays
   if (length < INSERTION_SORT_THRESHOLD) {
   // Insertion sort
   ......
   }

3.用公式length/8+length/64+1近似计算出数组长度的1/7。

1
2
// Inexpensive approximation of length / 7
   int seventh = (length >> 3) + (length >> 6) + 1;

4.取5个根据经验得出的等距点。

1
2
3
4
5
6
7
8
9
10
11
12
/*
    * Sort five evenly spaced elements around (and including) the
    * center element in the range. These elements will be used for
    * pivot selection as described below. The choice for spacing
    * these elements was empirically determined to work well on
    * a wide variety of inputs.
    */
   int e3 = (left + right) >>> 1; // The midpoint
   int e2 = e3 - seventh;
   int e1 = e2 - seventh;
   int e4 = e3 + seventh;
   int e5 = e4 + seventh;

5.将这5个元素进行插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Sort these elements using insertion sort
    if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
    if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
    }
    if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
        if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
        }
    }
    if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
        if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
            }
        }
    }

6.选取a[e2]，a[e4]分别作为pivot1，pivot2。由于步骤5进行了排序，所以必有pivot1 <=pivot2。定义两个指针less和great，less从最左边开始向右遍历，一直找到第一个不小于pivot1的元素，great从右边开始向左遍历，一直找到第一个不大于pivot2的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
        * Use the second and fourth of the five sorted elements as pivots.
        * These values are inexpensive approximations of the first and
        * second terciles of the array. Note that pivot1 <= pivot2.
        */
       int pivot1 = a[e2];
       int pivot2 = a[e4];
       /*
        * The first and the last elements to be sorted are moved to the
        * locations formerly occupied by the pivots. When partitioning
        * is complete, the pivots are swapped back into their final
        * positions, and excluded from subsequent sorting.
        */
       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);

7.接着定义指针k从less-1开始向右遍历至

great，把小于pivot1的元素移动到less左边，大于pivot2的元素移动到great右边。这里要注意，我们已知great处的元素小于pivot2，但是它于pivot1的大小关系，还需要进行判断，如果比pivot1还小，需要移动到到less左边，否则只需要交换到k处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * 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.
 */
        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];
                /*
                 * Here and below we use "a[i] = b; i++;" instead
                 * of "a[i++] = b;" due to performance issue.
                 */
                a[less] = ak;
                ++less;
            } else if (ak > pivot2) { // Move a[k] to right part
                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;
            }
        }

8.将less-1处的元素移动到队头，great+1处的元素移动到队尾，并把pivot1和pivot2分别放到less-1和great+1处。

1
2
3
// Swap pivots into their final positions
        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
        a[right] = a[great + 1]; a[great + 1] = pivot2;

9.至此，less左边的元素都小于pivot1，great右边的元素都大于pivot2，分别对两部分进行同样的递归排序。

1
2
3
// Sort left and right parts recursively, excluding known pivots
        sort(a, left, less - 2, leftmost);
        sort(a, great + 2, right, false);

10.对于中间的部分，如果大于4/7的数组长度，很可能是因为重复元素的存在，所以把less向右移动到第一个不等于pivot1的地方，把great向左移动到第一个不等于pivot2的地方，然后再对less和great之间的部分进行递归排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
         * If center part is too large (comprises > 4/7 of the array),
         * swap internal pivot values to ends.
         */
        if (less < e1 && e5 < great) {
            /*
             * Skip elements, which are equal to pivot values.
             */
            while (a[less] == pivot1) {
                ++less;
            }
            while (a[great] == pivot2) {
                --great;
            }
        }
        ......
        // Sort center part recursively
        sort(a, less, great, false);

另外参考了其他博文，算法思路如下：
算法步骤
1.对于很小的数组（长度小于47），会使用插入排序。
2.选择两个点P1,P2作为轴心，比如我们可以使用第一个元素和最后一个元素。
3.P1必须比P2要小，否则将这两个元素交换，现在将整个数组分为四部分：
（1）第一部分：比P1小的元素。
（2）第二部分：比P1大但是比P2小的元素。
（3）第三部分：比P2大的元素。
（4）第四部分：尚未比较的部分。
在开始比较前，除了轴点，其余元素几乎都在第四部分，直到比较完之后第四部分没有元素。
4.从第四部分选出一个元素a[K]，与两个轴心比较，然后放到第一二三部分中的一个。
5.移动L，K，G指向。
6.重复 4 5 步，直到第四部分没有元素。
7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。
8.递归的将第一二三部分排序。

总结：Arrays.sort对升序数组、降序数组和重复数组的排序效率有了很大的提升，这里面有几个重大的优化。
1.对于小数组来说，插入排序效率更高，每次递归到小于47的大小时，用插入排序代替快排，明显提升了性能。
2.双轴快排使用两个pivot，每轮把数组分成3段，在没有明显增加比较次数的情况下巧妙地减少了递归次数。
3.pivot的选择上增加了随机性，却没有带来随机数的开销。
4.对重复数据进行了优化处理，避免了不必要交换和递归。

img

　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.），要转回快速排序。