正面剛算法-Java中Arrays.sort()(一)

最近一直在看關(guān)于排序相關(guān)的算法，從O(n2)的冒泡、插入、選擇到O(nlog(n))的歸并、快排、再到桶排序、計(jì)數(shù)排序、基數(shù)排序。各個(gè)算法都有自己的優(yōu)點(diǎn)和缺點(diǎn)，那么jdk中關(guān)于這種底層的算法是怎么實(shí)現(xiàn)的呢？參考了一些博客，今天把學(xué)習(xí)到的東西總結(jié)一下。首先可以明確的是在java中的Arrays.sort()不僅僅使用了一種算法，他會(huì)根據(jù)數(shù)據(jù)不同的狀態(tài)選擇認(rèn)為合適的算法。

本文涉及

1.java中Arrays.sort()方法對(duì)于數(shù)據(jù)排序的流程
2.sort方法中涉及到的排序算法（插入、快排、歸并等）

一 java中Arrays.sort()排序流程

該方法簽名為：

// 僅以int[] 排序?yàn)槔?   public static void sort(int[] a) {
    // 調(diào)用的包內(nèi)排序算法為DualPivotQuicksort 稱(chēng)為雙軸快排
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

通過(guò)調(diào)用我們發(fā)現(xiàn)是調(diào)用 DualPivotQuicksort.sort()方法。
那么Arrays.sort是不是就是直接使用DualPivotQuicksort 這種指定算法呢？
答案是否定的，我先把梳理出來(lái)的流程圖放到前面，之后在分析一下各情況的判斷

Arrays.sort處理流程

處理。

  • 首先當(dāng)元素個(gè)數(shù)低于QUICKSORT_THRESHOLD（286）時(shí)，直接進(jìn)入private static void sort(int[] a, int left, int right, boolean leftmost)方法，該方法后面我們?cè)诓鸾?/li> 
      // Use Quicksort on small arrays
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }
  • 當(dāng)元素個(gè)數(shù)大于286個(gè)時(shí)，會(huì)進(jìn)行數(shù)據(jù)的亂序的程度排查,結(jié)果有四種：
    ①出現(xiàn)連續(xù)的相同值（33個(gè)），也直接執(zhí)行 private static void sort(int[] a, int left, int right, boolean leftmost)方法；
    ②數(shù)據(jù)中升降序的切換次數(shù)（計(jì)算出的count值。count值為run[]中的使用位數(shù)，一個(gè)run[]中的一位代表一段數(shù)據(jù)中，數(shù)據(jù)是有序的，升、降）大于67（時(shí)），直接執(zhí)行 private static void sort(int[] a, int left, int right, boolean leftmost)方法；
    ③當(dāng)數(shù)據(jù)中升降序的切換次數(shù)（計(jì)算出的count值。count值為run[]中的使用位數(shù)，一個(gè)run[]中的一位代表一段數(shù)據(jù)中，數(shù)據(jù)是有序的，升、降）小于67（時(shí)），完成循環(huán)；
    ④已經(jīng)完全有序，完成循環(huán)（在這之后會(huì)進(jìn)行結(jié)束排序）；
       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;
           }
       }

我們來(lái)看一下這段check代碼

  1. int[] run：排序區(qū)間數(shù)組，每一個(gè)run代表一個(gè)有序子數(shù)組元素?cái)?shù)量
  2. k：游標(biāo)，標(biāo)記元素
  3. count:run區(qū)間使用數(shù)
  4. int m：連續(xù)相同元素個(gè)數(shù)指標(biāo)
    從這中段代碼，我們可以看出，數(shù)組的排序情況已經(jīng)元素的相似度都會(huì)影響算法的使用。

上面代碼執(zhí)行完畢，沒(méi)有觸發(fā)執(zhí)行其中的return，則會(huì)執(zhí)行下面代碼，下面代碼分為執(zhí)行歸并處理和該數(shù)據(jù)完全有序直接返回的處理

        // 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;
        }

上面代碼會(huì)進(jìn)行完全有序直接返回的操作，或者補(bǔ)充最后一個(gè)有序區(qū)間為一個(gè)元素的統(tǒng)計(jì)的情況，進(jìn)行接下來(lái)的操作。

接下來(lái)的代碼就屬于Arrays.sort中的歸并排序（優(yōu)化過(guò)的）的核心代碼，這里不展開(kāi)描述，會(huì)在另外的文章中，專(zhuān)門(mén)講解涉及到的基礎(chǔ)排序算法，這里只梳理排序的處理邏輯。

之前調(diào)用private static void sort(int[] a, int left, int right, boolean leftmost)的排序方法，其中會(huì)根據(jù)數(shù)據(jù)情況演變?yōu)?strong>雙軸快排、單軸快排，傳統(tǒng)插入排序、成對(duì)插入排序這幾種情況。

// leftmost 標(biāo)明數(shù)據(jù)范圍是否為最左側(cè)的數(shù)據(jù)，是否是起始位
private static void sort(int[] a, int left, int right, boolean leftmost)

首先映入眼簾的就是，一組插入排序，為什么叫一組，因?yàn)?，?dāng)數(shù)據(jù)為起始位數(shù)據(jù)采用傳統(tǒng)插入排序，非起始位（非最左側(cè)部分）采用成對(duì)插入排序（pair insertion sort）

 // Use insertion sort on tiny arrays
        if (length < INSERTION_SORT_THRESHOLD) {
            if (leftmost) {
                /*
                 * 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;
                }
            } else {
                /*
                 * Skip the longest ascending sequence.
                 */
                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;
            }
            return;
        }

當(dāng)數(shù)據(jù)規(guī)模和格式需要使用快排時(shí)，則會(huì)在數(shù)據(jù)中平均選取5個(gè)數(shù)據(jù)點(diǎn)，如果他們不存在相同元素則采用雙軸快排，如果存在則采用單軸快排
簡(jiǎn)略代碼如下：

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

        /*
         * 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;
        // e1~e5 排序

//============================

 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
            /*
             * 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];
            // 雙軸排序過(guò)程
else {
            int pivot = a[e3];
            // 單軸排序過(guò)程
}

其中有一個(gè)計(jì)算步驟很為巧妙，就是關(guān)于該數(shù)組最接近1/7的值的計(jì)算，一般我們可能會(huì)采用int minSeventh = length/7 這樣直接計(jì)算出長(zhǎng)度的1/7的近似值。但作者采用的位運(yùn)算進(jìn)行計(jì)算，我思前想后也沒(méi)有想出來(lái)為什么這樣寫(xiě)，直到看到知乎上一個(gè)回答，才有眉目。

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

這里面有逼近求解的思想和使用位運(yùn)算替代除法的思想。

首先我們大致可以將"m >> n" 右位移運(yùn)算當(dāng)做是m除以2的n次方；

length >> 3 等于length/(2的3次方)  = length/8 ;
length >> 6 等于 length/62

那么在看這個(gè)表達(dá)式就變成了：

int seventh = length/8 + length/62 + 1

我們需要的是length/7當(dāng)我們知道length/8 的值之后，可以補(bǔ)上
length/7-length/8的差值，就可以求出來(lái)length/7。

length/7 = length/8 + (length/7 -length/8)
length/7-length/8 = length/56。

和length/56最近的一個(gè)位運(yùn)算結(jié)果就是length/62。
綜上求length/7的近似值可以寫(xiě)成

int seventh = length/8 + length/62 + 1

至于最后的+1，是為了彌補(bǔ)兩次位運(yùn)算的期望值補(bǔ)償。最后的補(bǔ)償選擇別人的結(jié)論為，+1補(bǔ)償優(yōu)于不補(bǔ)償?shù)木取?/p>

如果我們不考慮其中具體排序算法，Arrays.sort()流程分析基本就結(jié)束了，后面針對(duì)每個(gè)算法的實(shí)現(xiàn)會(huì)單獨(dú)進(jìn)行分析記錄。

二 Arrays.sort方法中涉及的排序算法

  • 傳統(tǒng)插入排序
  • 成對(duì)插入排序
  • 單軸快速排序
  • 雙軸快速排序
  • 歸并排序優(yōu)化版，其中隱約看到計(jì)數(shù)排序的影子（個(gè)人愚見(jiàn)）
附：參考內(nèi)容：

JDK源碼DualPivotQuicksort類(lèi)中利用移位求除7近似值？
Java SDK中的sort算法小議 - 03 雙軸快排

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容