http://blog.csdn.net/lingzhm/article/details/45022385

参考自：论文，Dual-Pivot Quicksort algorithm ，by Vladimir Yaroslavskiy。

http://www.sytarena.com/javajswz/20140217/1329.html

转载自：http://blog.csdn.NET/jy3161286/article/details/23361191?utm_source=tuicool

DualPivotQuicksort是JDK1.7开始的采用的快速排序算法。

一般的快速排序采用一个枢轴来把一个数组划分成两半，然后递归之。

大量经验数据表面，采用两个枢轴来划分成3份的算法更高效，这就是DualPivotQuicksort。

算法思想

选出两个枢轴P1和P2，需要3个指针L,K,G。
3个指针的作用如下图：

算法为以下的步骤：
1、小于27的数组，使用插入排序(或47)。
2、选择枢轴P1和P2。(假设使用数组头和尾)。
3、P1需要小于P2，否者交换。
现在数组被分成4份，left到L的小于P1的数，L到K的大于P1小于P2的数，G到rigth的大于P2的数，待处理的K到G的中间的数(逐步被处理到前3个区域中)。
4、L从开始初始化直至不小于P1，K初始化为L-1，G从结尾初始化直至不大于P2。K是主移动的指针，来一步一步吞噬中间区域。
****当大于P1小于P2，K++。
****当小于P1，交换L和K的数，L++,K++。
****当大于P2，如果G的数小于P1，把L上的数放在K上，把G的数放在L上，L++，再把K以前的数放在G上，G--，K++，完成一次L,K,G的互相交换。否则交换K和G，并G--，K++。
5、递归4。
6、交换P1到L-1上。交换P2到G+1上。
7、递归之。

JDK源码 

流程图：

TimSort

直接调用的sort第一级：
[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. public static void sort(int[] a, int left, int right) {  
  2.     // Use Quicksort on small arrays  
  3.     if (right - left < QUICKSORT_THRESHOLD) {//门限为286  
  4.         sort(a, left, right, true);  
  5.         return;  
  6.     }  
  7.   
  8.     /* 
  9.      * Index run[i] is the start of i-th run 
  10.      * (ascending&nbs***bsp;descending sequence). 
  11.      */  
  12.     int[] run = new int[MAX_RUN_COUNT + 1];  
  13.     int count = 0; run[0] = left;  
  14.   
  15.     // Check if the array is nearly sorted  
  16.     for (int k = left; k < right; run[count] = k) {  
  17.         if (a[k] < a[k + 1]) { // ascending  
  18.             while (++k <= right && a[k - 1] <= a[k]);  
  19.         } else if (a[k] > a[k + 1]) { // descending  
  20.             while (++k <= right && a[k - 1] >= a[k]);  
  21.             for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {  
  22.                 int t = a[lo]; a[lo] = a[hi]; a[hi] = t;  
  23.             }  
  24.         } else { // equal  
  25.             for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {  
  26.                 if (--m == 0) {  
  27.                     sort(a, left, right, true);  
  28.                     return;  
  29.                 }  
  30.             }  
  31.         }  
  32.   
  33.         /* 
  34.          * The array is not highly structured, 
  35.          * use Quicksort instead of merge sort. 
  36.          */  
  37.         if (++count == MAX_RUN_COUNT) {  
  38.             sort(a, left, right, true);  
  39.             return;  
  40.         }  
  41.     }  
  42.   
  43.     // Check special cases  
  44.     if (run[count] == right++) { // The last run contains one element  
  45.         run[++count] = right;  
  46.     } else if (count == 1) { // The array is already sorted  
  47.         return;  
  48.     }  
  49.   
  50.     /* 
  51.      * Create temporary array, which is used for merging. 
  52.      * Implementation note: variable "right" is increased by 1. 
  53.      */  
  54.     int[] b; byte odd = 0;  
  55.     for (int n = 1; (n <<= 1) < count; odd ^= 1);  
  56.   
  57.     if (odd == 0) {  
  58.         b = a; a = new int[b.length];  
  59.         for (int i = left - 1; ++i < right; a[i] = b[i]);  
  60.     } else {  
  61.         b = new int[a.length];  
  62.     }  
  63.   
  64.     // Merging  
  65.     for (int last; count > 1; count = last) {  
  66.         for (int k = (last = 0) + 2; k <= count; k += 2) {  
  67.             int hi = run[k], mi = run[k - 1];  
  68.             for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {  
  69.                 if (q >= hi || p < mi && a[p] <= a[q]) {  
  70.                     b[i] = a[p++];  
  71.                 } else {  
  72.                     b[i] = a[q++];  
  73.                 }  
  74.             }  
  75.             run[++last] = hi;  
  76.         }  
  77.         if ((count & 1) != 0) {  
  78.             for (int i = right, lo = run[count - 1]; --i >= lo;  
  79.                 b[i] = a[i]  
  80.             );  
  81.             run[++last] = right;  
  82.         }  
  83.         int[] t = a; a = b; b = t;  
  84.     }  
  85. }  
1、当小于286时，直接使用双枢轴快速排序。
2、大于286时，先使用TimSort的思想，找出正序或者倒序的数(run的栈)，然后合并各个run，最后完成TimSort。
3、在找出run的时候，找出的run个数大于67时，即认为它是一个比较乱序的数组，就直接采用双枢轴快速排序。

双元素插入排序

下面看看双枢轴快速排序的实现(代码太长，分解之)：
[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. /** 
  2.  * Sorts the specified range of the array by Dual-Pivot Quicksort. 
  3.  * 
  4.  * @param a the array to be sorted 
  5.  * @param left the index of the first element, inclusive, to be sorted 
  6.  * @param right the index of the last element, inclusive, to be sorted 
  7.  * @param leftmost indicates if this part is the leftmost in the range 
  8.  */  
  9. private static void sort(int[] a, int left, int right, boolean leftmost) {  
  10.     int length = right - left + 1;  
  11.   
  12.     // Use insertion sort on tiny arrays  
  13.     if (length < INSERTION_SORT_THRESHOLD) {//47个  
  14.         if (leftmost) {  
  15.             /* <li style="border-top: none; border-right: none; border-bottom: none; border-left: 3px solid rgb(108, 226, 108); border-image: initial; list-style-type: decimal-leading-zero; list-style-image: initial; background-color: rgb(248, 248, 248); line-he