轉(zhuǎn)載：解析Arrays中sort方法的黑科技

排序問(wèn)題是算法里面的經(jīng)典問(wèn)題，也是計(jì)算機(jī)學(xué)科數(shù)據(jù)結(jié)構(gòu)課程里面的必修課，面對(duì)諸多的如插入排序，快速排序，堆排序，歸并排序等等經(jīng)典排序算法，JDK的實(shí)現(xiàn)者是如何選擇排序算法的呢？我們經(jīng)常使用的對(duì)數(shù)據(jù)進(jìn)行排序的算法Arrays.sort，Collections.sort方法，那么具體它們是如何實(shí)現(xiàn)的呢，本文嘗試從jdk 1.8的實(shí)現(xiàn)源碼上進(jìn)行分析，學(xué)習(xí)在實(shí)際工業(yè)環(huán)境下對(duì)排序算法的使用方法。

概述

Collections的sort方法的實(shí)現(xiàn)最終調(diào)用了Arrays的sort方法，所以我們僅僅分析Arrays中的sort方法，這一節(jié)，我們嘗試從宏觀的角度來(lái)看Arrays的sort方法。Arrays的sort方法分為兩種：基本類(lèi)型和Object類(lèi)型。他們的實(shí)現(xiàn)方法不同。

基本類(lèi)型：

我們從Arrays.sort(int[])方法來(lái)概述基本類(lèi)型排序的基本思路：

• 1. 如果數(shù)組元素個(gè)數(shù)小于NSERTION_SORT_THRESHOLD(47),那么使用改進(jìn)的插入排序進(jìn)行排序
• 2. 如果元素個(gè)數(shù)大于插入排序的閾值并且小于快速排序的閾值QUICKSORT_THRESHOLD(286)，則使用改進(jìn)的雙軸快速排序進(jìn)行排序
• 3. 如果元素個(gè)數(shù)大于快速排序的閾值，根據(jù)數(shù)組的無(wú)序程度來(lái)判定繼續(xù)使用哪種算法，無(wú)序程度通過(guò)將數(shù)組劃分為不同的有序序列的個(gè)數(shù)來(lái)判定，如果有序序列的個(gè)數(shù)大于MAX_RUN_COUNT(67),則認(rèn)為原數(shù)組基本無(wú)序,則仍然使用雙軸快速排序，如果小于MAX_RUN_COUNT，則認(rèn)為原數(shù)組基本有序，使用歸并排序進(jìn)行排序。

Object對(duì)象類(lèi)型：

我們從Arrays.sort(Object[])的實(shí)現(xiàn)來(lái)概述Object對(duì)象類(lèi)型的排序，其基本思路是：

• 1. 如果數(shù)組元素個(gè)數(shù)小于MIN_MERGE(32),那么就會(huì)調(diào)用二分插入排序binarySort方法進(jìn)行排序，所謂二分排序，是指在插入的過(guò)程中，使用二分查找的方法查找待插入的位置，這種查找方法會(huì)比線性查找快一點(diǎn)。
• 2. 如果大于MIN_MERGE，則將數(shù)組劃分成多個(gè)有序塊進(jìn)行歸并排序。

綜上所述，無(wú)論是基本類(lèi)型的排序還是Object類(lèi)型的排序，都使用了多種排序的組合，這種組合的原因在于在不同的排序規(guī)模下，需要適應(yīng)性的選用不同的排序方法，例如，在排序規(guī)模較小的情況下，復(fù)雜度為O(n^2)的插入排序能獲得比例如快速排序更好的排序性能，而在數(shù)組基本有序的情況下，歸并排序比快速排序相比是更好的選擇。總的來(lái)說(shuō)，根據(jù)不同的數(shù)組規(guī)模決定使用不同的排序方法。接下來(lái)我們通過(guò)詳細(xì)的代碼分析其具體實(shí)現(xiàn)。

基本類(lèi)型排序(Arrays.sort(int[]))

Arrays的sort方法直接調(diào)用了DualQivotQuicksort的sort方法，類(lèi)名的英語(yǔ)意思是雙軸快速排序。可見(jiàn)雙軸快速排序是關(guān)鍵。

接下來(lái)進(jìn)入sort方法，通過(guò)英語(yǔ)注釋我們可以看到第一步，如果數(shù)組長(zhǎng)度較小的話（小于QUICKSORT_THRESHOLD）,則使用sort方法進(jìn)行排序，執(zhí)行完方法結(jié)束。

if (length < INSERTION_SORT_THRESHOLD) {
      if (leftmost) {//默認(rèn)情況下，經(jīng)典插入排序
          /*
           * 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 {//否則，使用改進(jìn)后的成對(duì)插入排序
          /*
           * 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;
  }

如果不是小于INSERTION_SORT_THRESHOLD，則使用5分位法找出5個(gè)位置的值做雙軸快速排序

否則的話，就使用第三個(gè)點(diǎn)進(jìn)行單軸快速排序

以上是數(shù)組長(zhǎng)度小于QUICKSORT_THRESHOLD（286）時(shí)候的排序策略，如果大于這個(gè)快速排序的閾值，又是怎么做的呢，我們繼續(xù)往下看源碼，發(fā)現(xiàn)這么一段代碼，其目的也很明確，就是檢查原來(lái)數(shù)組是不是基本有序，方法是找出有序的數(shù)組片段，用count進(jìn)行統(tǒng)計(jì)，如果count一旦等于MAX_RUN_COUNT，則認(rèn)為基本無(wú)序，使用我們上面提到的方法進(jìn)行快速排序。

基本無(wú)序狀態(tài)檢查

在上面統(tǒng)計(jì)count的過(guò)程中，同樣使用run數(shù)組記錄所有的基本有序的數(shù)組的最后一個(gè)元素的下標(biāo)，如果判定結(jié)果是基本有序，則使用的歸并排序進(jìn)行最終的排序，方法是通過(guò)run方法記錄的下標(biāo)每次合并兩個(gè)有序序列，最終使得數(shù)組有序，這里就不貼出很長(zhǎng)的歸并代碼。
基本上，基礎(chǔ)類(lèi)型的排序算法就這樣講完了。

Object類(lèi)型排序(Arrays.sort(Object[]))

Arrays.sort方法的Object數(shù)組要求實(shí)現(xiàn)Comparable接口，因?yàn)樵谄鋵?shí)現(xiàn)過(guò)程中有
Object類(lèi)型的排序中l(wèi)egacyMergeSort是經(jīng)典的歸并排序，不過(guò)它即將被廢棄了，這里只是用來(lái)兼容老的排序方法，現(xiàn)在默認(rèn)使用的是ComparableSort里面的sort方法，我們的分析著重在這個(gè)方法。

首先，如果數(shù)組的長(zhǎng)度小于MIN_MERGE(32),那么就會(huì)調(diào)用二分插入排序binarySort方法進(jìn)行排序，所謂二分排序，是指在插入的過(guò)程中，使用二分查找的方法查找待插入的位置，這種查找方法會(huì)比線性查找快一點(diǎn)。

參考文獻(xiàn)

• Java源碼閱讀-DualPivotQuicksort
• 數(shù)據(jù)數(shù)組排序：Arrays.sort()
• 單軸快排（SinglePivotQuickSort）和雙軸快排（DualPivotQuickSort）及其JAVA實(shí)現(xiàn)
• Arrays.sort()方法的源碼分析