解析Arrays中sort方法的黑科技

排序问题是算法里面的经典问题，也是计算机学科数据结构课程里面的必修课，面对诸多的如插入排序，快速排序，堆排序，归并排序等等经典排序算法，JDK的实现者是如何选择排序算法的呢？我们经常使用的对数据进行排序的算法Arrays.sort，Collections.sort方法，那么具体它们是如何实现的呢，本文尝试从jdk 1.8的实现源码上进行分析，学习在实际工业环境下对排序算法的使用方法。

概述

Collections的sort方法的实现最终调用了Arrays的sort方法，所以我们仅仅分析Arrays中的sort方法，这一节，我们尝试从宏观的角度来看Arrays的sort方法。Arrays的sort方法分为两种：基本类型和Object类型。他们的实现方法不同
我们从Arrays.sort(int[])方法来概述基本类型排序的基本思路：1.如果数组元素个数小于NSERTION_SORT_THRESHOLD(47),那么使用改进的插入排序进行排序，2.如果元素个数大于插入排序的阈值并且小于快速排序的阈值QUICKSORT_THRESHOLD(286)，则使用改进的双轴快速排序进行排序，3.如果元素个数大于快速排序的阈值，根据数组的无序程度来判定继续使用哪种算法，无序程度通过将数组划分为不同的有序序列的个数来判定，如果有序序列的个数大于MAX_RUN_COUNT(67),则认为原数组基本无序,则仍然使用双轴快速排序，如果小于MAX_RUN_COUNT，则认为原数组基本有序，使用归并排序进行排序。
我们从Arrays.sort(Object[])的实现来概述Object对象类型的排序，其基本思路是：1.如果数组元素个数小于MIN_MERGE(32),2.如果大于MIN_MERGE，则将数组划分成多个有序块进行归并排序。
综上所述，无论是基本类型的排序还是Object类型的排序，都使用了多种排序的组合，这种组合的原因在于在不同的排序规模下，需要适应性的选用不同的排序方法，例如，在排序规模较小的情况下，复杂度为O(n^2)的插入排序能获得比例如快速排序更好的排序性能，而在数组基本有序的情况下，归并排序比快速排序相比是更好的选择。总的来说，根据不同的数组规模决定使用不同的排序方法。接下来我们通过详细的代码分析其具体实现。

基本类型排序(Arrays.sort(int[]))

Arrays的sort方法直接调用了DualQivotQuicksort的sort方法，类名的英语意思是双轴快速排序。可见双轴快速排序是关键。

接下来进入sort方法，通过英语注释我们可以看到第一步，如果数组长度较小的话（小于QUICKSORT_THRESHOLD）,则使用sort方法进行排序，执行完方法结束。

那么sort方法又是如何排序的，判断数组长度是否小于INSERTION_SORT_THRESHOLD，如果是的话，则使用插入排序，并且在插入排序使用leftmost控制使用传统的插入排序还是改进的插入排序。改进的插入排序被称为成对插入排序（pair insertion sort）,其基本思想是一次取出两个未排序数组的元素，并且确保（a1>a2）,那么在a1找到位置后，a2的位置肯定在a1之前，继续查找即可。

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

如果不是小于INSERTION_SORT_THRESHOLD，则使用5分位法找出5个位置的值做双轴快速排序

这里有必要解释一下双轴快速排序，双轴快速排序的思想是相对于单轴快速排序，经典的单轴快速排序，每次选择一个元素作为轴值pivot,然后使用双指针将小于pivot移到pivot的左边，大于pivot的值移到右边，使得pivot处于最终位置，这个过程称为一次排序，对两边递归的调用一次排序可以得到最终的排序结果。
而双轴快速排序的基本思想是一次可以将两个元素放到最终位置上，假设这两个轴值为pivot1,pivot2,那么一次排序后，最终数组被这两个元素划分成三块：<pivot1, >=pivot1并且<=pivot2, >pivot2。为了达到这种划分，我们需要三个指针来进行操作i,k,j,i左边的是小于pivot1的，j右边的是大于pivot1的，k用来扫描，当k和j相聚的时候，则扫描结束。关于双轴快速排序的具体实现可以参考这篇文章《单轴快排（SinglePivotQuickSort）和双轴快排（DualPivotQuickSort）及其JAVA实现》这篇文章，写的很好。
相比单轴快速排序，双轴快速排序能够获取更快的排序效率，我们来看一看源码中的关键实现，从源码上来看，当5分位点所有值都不相同的时候，选取第二个点和第四个点作为双轴进行双轴快速排序。

否则的话，就使用第三个点进行单轴快速排序

以上是数组长度小于QUICKSORT_THRESHOLD（286）时候的排序策略，如果大于这个快速排序的阈值，又是怎么做的呢，我们继续往下看源码，发现这么一段代码，其目的也很明确，就是检查原来数组是不是基本有序，方法是找出有序的数组片段，用count进行统计，如果count一旦等于MAX_RUN_COUNT，则认为基本无序，使用我们上面提到的方法进行快速排序。

基本无序状态检查

在上面统计count的过程中，同样使用run数组记录所有的基本有序的数组的最后一个元素的下标，如果判定结果是基本有序，则使用的归并排序进行最终的排序，方法是通过run方法记录的下标每次合并两个有序序列，最终使得数组有序，这里就不贴出很长的归并代码。
基本上，基础类型的排序算法就这样讲完了。

Object类型排序(Arrays.sort(Object[]))

Arrays.sort方法的Object数组要求实现Comparable接口，因为在其实现过程中有
Object类型的排序中legacyMergeSort是经典的归并排序，不过它即将被废弃了，这里只是用来兼容老的排序方法，现在默认使用的是ComparableSort里面的sort方法，我们的分析着重在这个方法。

首先，如果数组的长度小于MIN_MERGE(32),那么就会调用二分插入排序binarySort方法进行排序，所谓二分排序，是指在插入的过程中，使用二分查找的方法查找待插入的位置，这种查找方法会比线性查找快一点。

如果不答应MIN_MERGE，则使用归并排序，归并的方法是将数组换分成等块的小数组(除最后一块)，在小数组内进行二分插入排序，排序后将当前数组的初始位置，长度使用pushRun方法压栈，mergeCollapse方法每次会从数组中取出两个小数组进行归并排序，最终循环结束后，数组也已经排序完成。

嗯，基本上就是这样了