Java中的Arrays.sort(int[])_arrays.sort int[]

Arrays.sort(int[])

Arrays.sort(int[])使用的是quicksort+merge sort。

• 使用quicksort：当数组长度比较小（right-left<286），或者数组有序的程度不是很高（有序子数组个数>=67个），或者有较多的相等元素（连续33个元素相等）使用quicksort。
• 使用mergesort：当数组长度较长且有序程度较高时，使用。

总结来说，当数组中连续相等的数>=MAX_RUN_LENGTH（33）个时，执行quickSort；当for循环执行次数>=67时，说明数组中的连续子串数目较多（换句话说，在数组长度固定下，每个连续子串的长度较短），有序程度低，执行queckSort。否则，执行mergeSort，

static void sort(int[] a, int left, int right,
                     int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays，QUICKSORT_THRESHOLD=286
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }
 
        /*
         * Index run[i] is the start of i-th run
         * (ascending or descending sequence).
         */
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;
 
        // 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，当有MAX_RUN_LENGTH=33个值连续相等时，使用quicksort
                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.
             */
            // 当count==MAX_RUN_COUNT（67）时，说明已经遍历了67个连续的子序列，这说明数组有序程度不高，使用quicksort
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }
 
        // 如果在count < MAX_RUN_COUNT(67)的时候，即for循环执行次数少于67次就遍历完了a[]，那就说明a[]的有序程度很高，进行merge sort
        ......
}

Arrays.sort(int[])使用的quickSort

这个排序算法NB了，其它的快排算法在测试大量数据集的时候，时间复杂度退化到O（n^2），而这个Dual-privot Quicksort依旧能保持O(n logn)的时间复杂度，代码以后有时间再看吧。

* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.

代码分析...