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

本文涉及

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

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

該方法簽名為：

// 僅以int[] 排序為例
   public static void sort(int[] a) {
    // 調用的包內排序算法為DualPivotQuicksort 稱為雙軸快排
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

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

Arrays.sort處理流程

處理。

• 首先當元素個數低于QUICKSORT_THRESHOLD（286）時，直接進入private static void sort(int[] a, int left, int right, boolean leftmost)方法，該方法后面我們在拆解

      // Use Quicksort on small arrays
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

• 當元素個數大于286個時，會進行數據的亂序的程度排查,結果有四種：
  ①出現連續(xù)的相同值（33個），也直接執(zhí)行 private static void sort(int[] a, int left, int right, boolean leftmost)方法；
  ②數據中升降序的切換次數（計算出的count值。count值為run[]中的使用位數，一個run[]中的一位代表一段數據中，數據是有序的，升、降）大于67（時），直接執(zhí)行 private static void sort(int[] a, int left, int right, boolean leftmost)方法；
  ③當數據中升降序的切換次數（計算出的count值。count值為run[]中的使用位數，一個run[]中的一位代表一段數據中，數據是有序的，升、降）小于67（時），完成循環(huán)；
  ④已經完全有序，完成循環(huán)（在這之后會進行結束排序）；

       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代碼

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

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

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

上面代碼會進行完全有序直接返回的操作，或者補充最后一個有序區(qū)間為一個元素的統計的情況，進行接下來的操作。

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

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

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

首先映入眼簾的就是，一組插入排序，為什么叫一組，因為，當數據為起始位數據采用傳統插入排序，非起始位（非最左側部分）采用成對插入排序（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;
        }

當數據規(guī)模和格式需要使用快排時，則會在數據中平均選取5個數據點，如果他們不存在相同元素則采用雙軸快排，如果存在則采用單軸快排
簡略代碼如下：

 // 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];
            // 雙軸排序過程
else {
            int pivot = a[e3];
            // 單軸排序過程
}

其中有一個計算步驟很為巧妙，就是關于該數組最接近1/7的值的計算，一般我們可能會采用int minSeventh = length/7 這樣直接計算出長度的1/7的近似值。但作者采用的位運算進行計算，我思前想后也沒有想出來為什么這樣寫，直到看到知乎上一個回答，才有眉目。

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

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

首先我們大致可以將"m >> n" 右位移運算當做是m除以2的n次方；

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

那么在看這個表達式就變成了：

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

我們需要的是length/7當我們知道length/8 的值之后，可以補上
length/7-length/8的差值，就可以求出來length/7。

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

和length/56最近的一個位運算結果就是length/62。
綜上求length/7的近似值可以寫成

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

至于最后的+1，是為了彌補兩次位運算的期望值補償。最后的補償選擇別人的結論為，+1補償優(yōu)于不補償的精度。

如果我們不考慮其中具體排序算法，Arrays.sort()流程分析基本就結束了，后面針對每個算法的實現會單獨進行分析記錄。

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

• 傳統插入排序
• 成對插入排序
• 單軸快速排序
• 雙軸快速排序
• 歸并排序優(yōu)化版，其中隱約看到計數排序的影子（個人愚見）

附：參考內容：

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