快捷導(dǎo)航

Arrays.sort(arr)是什么排序及代碼邏輯

更新時間：2022年02月02日 09:55:36 作者：可樂加品客

在學(xué)習(xí)過程中觀察到Arrays.sort(arr)算法可以直接進行排序，但不清楚底層的代碼邏輯是什么樣子，今天通過本文給大家介紹下Arrays.sort(arr)是什么排序，感興趣的朋友一起看看吧

在學(xué)習(xí)過程中觀察到Arrays.sort(arr)算法可以直接進行排序，但不清楚底層的代碼邏輯是什么樣子，記得自己之前在面試題里面也有面試官問這個問題，只能說研究之后發(fā)現(xiàn)還是比較復(fù)雜的，并不是網(wǎng)上說的快排或者二分插入之類的。

首先看源碼：

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

它調(diào)用了DualPivotQuicksort的sort方法，乍一看以為是快排，這是很多網(wǎng)上的博主的說法，繼續(xù)點開向下看（代碼太長，沒耐心看可以直接跳過該段代碼QWQ）：

 static void sort(int[] a, int left, int right,
                     int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays
        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
                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;
            }
        }
        // Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }
        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);
        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }
        // 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;
        }
    }

代碼很長，簡要翻譯過來，這里分了好幾種情況：

1.數(shù)組長度小于286

這里又會調(diào)用一個sort方法，點開該sort()，又會劃分情況：

數(shù)組長度小于47，

當leftmost（導(dǎo)入的一個布爾參數(shù)）為true，則使用直接插入排序；

否則會調(diào)用另一種插入辦法，這里可以觀察到一個注釋：

/*
* 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.
*/

大致意思是：相鄰部分的每個元素都扮演著哨兵的角色，因此這允許我們避免在每次迭代中進行左范圍檢查。此外，我們使用了更優(yōu)化的算法，即所謂的成對插入排序，它比插入排序的傳統(tǒng)實現(xiàn)更快（在快速排序的上下文中）。

不過注意到，原函數(shù)參數(shù)傳參在這里leftmost為true，所以一定是直接插入排序，以上作為了解。

數(shù)組長度大于47，采用一種快速排序的辦法，這里因為代碼太長，學(xué)藝不精，參考了一下http://m.fzitv.net/article/236440.htm:

至于大過INSERTION_SORT_THRESHOLD（47）的，用一種快速排序的方法：

1.從數(shù)列中挑出五個元素，稱為 “基準”（pivot）；

2.重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；

3.遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

當數(shù)組長度大于286時

此時回到那段很長很長的代碼段，在判斷小于286的長度數(shù)組之后，從注解中：

// Check if the array is nearly sorted

這里是指檢查數(shù)組元素是不是快要排列好了，或者書面一點說，是不是有一定結(jié)構(gòu)了，然后看后面的for循環(huán)，注意到一段代碼：

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

這里的sort和我們上面在數(shù)組長度小于286時的那個sort方法是同一個方法，而針對這個count，是用來記錄逆序組的，打個比方：

此時有一個數(shù)組為1 5 6 9 8 7 2 3

當數(shù)組認定我們的順序應(yīng)該為升序時，從第一個數(shù)開始數(shù)，此時9 8 7 2為降序，這就是逆序，將這四個數(shù)組合成一個組稱為逆序組，然后再從3開始往后看。

當統(tǒng)計到一個逆序組時，count++，所以可以看出，count是用來記逆序組的，那么逆序組越多，這個結(jié)構(gòu)就越混亂

MAX_RUN_COUNT == 67 ，因此當count一直加到67時，就說明已經(jīng)在一個混亂的臨界值了，此時執(zhí)行sort()方法

通過這一段分析，我們理一下思路：

?如果數(shù)組能運行到這里，說明數(shù)組的長度大于等于286。符合該條件時，我們要判斷這個數(shù)組是否有一定的結(jié)構(gòu)：

（1）count<67，說明不是那么混亂，有一定結(jié)構(gòu)，跳過；

（2）count>=67，說明已經(jīng)混亂了，沒有結(jié)構(gòu)，執(zhí)行sort方法，而已知數(shù)組長度大于等于286，那么必然大于47，一定執(zhí)行快速排序。

跳過之后，經(jīng)過代碼的一大堆前置操作，最后看見下面的代碼里面一行注釋：

//Merging

顯然，這里后面用到歸并排序了，不詳細贅述。

好了，最后總結(jié)：

數(shù)組長度小于286時，根據(jù)數(shù)組長度，分兩種情況：
- 數(shù)組長度小于47，使用直接插入排序
- 數(shù)組長度大于47，使用快速排序
數(shù)組長度大于286時，根據(jù)數(shù)組排序情況，分兩種情況：
- 數(shù)組內(nèi)順序較為混亂，即count逆序組數(shù)大于等于67，使用快速排序
- 數(shù)組內(nèi)有一定順序，即count逆序組數(shù)小于67，使用歸并排序