1. int[] nums = {1,24,6,7,23,6,2,4,7,9,3,53,123}
    2. Arrays.sort(nums);

    方法调用后，会进入DualPivotQuicksort.sort(nums, 0, nums.length - 1, null, 0, 0);方法，源码如下：

    1. static void sort(int[] a, int left, int right,
    2.                  int[] work, int workBase, int workLen) {
    3.     // Use Quicksort on small arrays
    4.     // 快排的阈值是 286, 数组长度低于 286 直接使用快排
    5.     if (right - left < QUICKSORT_THRESHOLD) {
    6.         sort(a, left, right, true);
    7.         return;
    8.     }
    10.     /*
    11.      * Index run[i] is the start of i-th run
    12.      * (ascending or descending sequence).
    13.      */
    14.     // 记录整个数组中有序部分的起点位置
    15.     int[] run = new int[MAX_RUN_COUNT + 1];
    16.     int count = 0; run[0] = left;
    18.     // Check if the array is nearly sorted
    19.     // 遍历整个数组, 令数组变的基本有序
    20.     for (int k = left; k < right; run[count] = k) {
    21.         if (a[k] < a[k + 1]) { // ascending
    22.             while (++k <= right && a[k - 1] <= a[k]);
    23.         } else if (a[k] > a[k + 1]) { // descending
    24.             while (++k <= right && a[k - 1] >= a[k]);
    25.             for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
    26.                 int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
    27.             }
    28.         } else { // equal
    29.             for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
    30.                 if (--m == 0) {
    31.                     sort(a, left, right, true);
    32.                     return;
    33.                 }
    34.             }
    35.         }
    37.         /*
    38.          * The array is not highly structured,
    39.          * use Quicksort instead of merge sort.
    40.          */
    41.         // 若有序度比较低, 就直接进行快排
    42.         if (++count == MAX_RUN_COUNT) {
    43.             sort(a, left, right, true);
    44.             return;
    45.         }
    46.     }
    48.     // Check special cases
    49.     // Implementation note: variable "right" is increased by 1.
    50.     // 最后一组的时候超出
    51.     if (run[count] == right++) { // The last run contains one element
    52.         run[++count] = right;
    53.     } else if (count == 1) { // The array is already sorted
    54.         return;
    55.     }
    57.     // Determine alternation base for merge
    58.     byte odd = 0;
    59.     for (int n = 1; (n <<= 1) < count; odd ^= 1);
    61.     // Use or create temporary array b for merging
    62.     int[] b;                 // temp array; alternates with a
    63.     int ao, bo;              // array offsets from 'left'
    64.     int blen = right - left; // space needed for b
    65.     if (work == null || workLen < blen || workBase + blen > work.length) {
    66.         work = new int[blen];
    67.         workBase = 0;
    68.     }
    69.     if (odd == 0) {
    70.         System.arraycopy(a, left, work, workBase, blen);
    71.         b = a;
    72.         bo = 0;
    73.         a = work;
    74.         ao = workBase - left;
    75.     } else {
    76.         b = work;
    77.         ao = 0;
    78.         bo = workBase - left;
    79.     }
    81.     // Merging
    82.     for (int last; count > 1; count = last) {
    83.         for (int k = (last = 0) + 2; k <= count; k += 2) {
    84.             int hi = run[k], mi = run[k - 1];
    85.             for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
    86.                 if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
    87.                     b[i + bo] = a[p++ + ao];
    88.                 } else {
    89.                     b[i + bo] = a[q++ + ao];
    90.                 }
    91.             }
    92.             run[++last] = hi;
    93.         }
    94.         if ((count & 1) != 0) {
    95.             for (int i = right, lo = run[count - 1]; --i >= lo;
    96.                 b[i + bo] = a[i + ao]
    97.             );
    98.             run[++last] = right;
    99.         }
    100.         int[] t = a; a = b; b = t;
    101.         int o = ao; ao = bo; bo = o;
    102.     }
    103. }

    快速排序源码：

    1. private static void sort(int[] a, int left, int right, boolean leftmost) {
    2.     int length = right - left + 1;
    4.     // Use insertion sort on tiny arrays
    5.     // 长度太小的话就用插入排序
    6.     if (length < INSERTION_SORT_THRESHOLD) {
    7.         if (leftmost) {
    8.             /*
    9.              * Traditional (without sentinel) insertion sort,
    10.              * optimized for server VM, is used in case of
    11.              * the leftmost part.
    12.              */
    13.             for (int i = left, j = i; i < right; j = ++i) {
    14.                 int ai = a[i + 1];
    15.                 while (ai < a[j]) {
    16.                     a[j + 1] = a[j];
    17.                     if (j-- == left) {
    18.                         break;
    19.                     }
    20.                 }
    21.                 a[j + 1] = ai;
    22.             }
    23.         } else {
    24.             /*
    25.              * Skip the longest ascending sequence.
    26.              */
    27.             do {
    28.                 if (left >= right) {
    29.                     return;
    30.                 }
    31.             } while (a[++left] >= a[left - 1]);
    33.             /*
    34.              * Every element from adjoining part plays the role
    35.              * of sentinel, therefore this allows us to avoid the
    36.              * left range check on each iteration. Moreover, we use
    37.              * the more optimized algorithm, so called pair insertion
    38.              * sort, which is faster (in the context of Quicksort)
    39.              * than traditional implementation of insertion sort.
    40.              */
    41.             for (int k = left; ++left <= right; k = ++left) {
    42.                 int a1 = a[k], a2 = a[left];
    44.                 if (a1 < a2) {
    45.                     a2 = a1; a1 = a[left];
    46.                 }
    47.                 while (a1 < a[--k]) {
    48.                     a[k + 2] = a[k];
    49.                 }
    50.                 a[++k + 1] = a1;
    52.                 while (a2 < a[--k]) {
    53.                     a[k + 1] = a[k];
    54.                 }
    55.                 a[k + 1] = a2;
    56.             }
    57.             int last = a[right];
    59.             while (last < a[--right]) {
    60.                 a[right + 1] = a[right];
    61.             }
    62.             a[right + 1] = last;
    63.         }
    64.         return;
    65.     }
    67.     // Inexpensive approximation of length / 7
    68.     int seventh = (length >> 3) + (length >> 6) + 1;
    70.     /*
    71.      * Sort five evenly spaced elements around (and including) the
    72.      * center element in the range. These elements will be used for
    73.      * pivot selection as described below. The choice for spacing
    74.      * these elements was empirically determined to work well on
    75.      * a wide variety of inputs.
    76.      */
    77.     int e3 = (left + right) >>> 1; // The midpoint
    78.     int e2 = e3 - seventh;
    79.     int e1 = e2 - seventh;
    80.     int e4 = e3 + seventh;
    81.     int e5 = e4 + seventh;
    83.     // Sort these elements using insertion sort
    84.     if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
    86.     if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
    87.         if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
    88.     }
    89.     if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
    90.         if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
    91.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
    92.         }
    93.     }
    94.     if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
    95.         if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
    96.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
    97.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
    98.             }
    99.         }
    100.     }
    102.     // Pointers
    103.     int less  = left;  // The index of the first element of center part
    104.     int great = right; // The index before the first element of right part
    106.     if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
    107.         /*
    108.          * Use the second and fourth of the five sorted elements as pivots.
    109.          * These values are inexpensive approximations of the first and
    110.          * second terciles of the array. Note that pivot1 <= pivot2.
    111.          */
    112.         int pivot1 = a[e2];
    113.         int pivot2 = a[e4];
    115.         /*
    116.          * The first and the last elements to be sorted are moved to the
    117.          * locations formerly occupied by the pivots. When partitioning
    118.          * is complete, the pivots are swapped back into their final
    119.          * positions, and excluded from subsequent sorting.
    120.          */
    121.         a[e2] = a[left];
    122.         a[e4] = a[right];
    124.         /*
    125.          * Skip elements, which are less or greater than pivot values.
    126.          */
    127.         while (a[++less] < pivot1);
    128.         while (a[--great] > pivot2);
    130.         /*
    131.          * Partitioning:
    132.          *
    133.          *   left part           center part                   right part
    134.          * +--------------------------------------------------------------+
    135.          * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
    136.          * +--------------------------------------------------------------+
    137.          *               ^                          ^       ^
    138.          *               |                          |       |
    139.          *              less                        k     great
    140.          *
    141.          * Invariants:
    142.          *
    143.          *              all in (left, less)   < pivot1
    144.          *    pivot1 <= all in [less, k)     <= pivot2
    145.          *              all in (great, right) > pivot2
    146.          *
    147.          * Pointer k is the first index of ?-part.
    148.          */
    149.         outer:
    150.         for (int k = less - 1; ++k <= great; ) {
    151.             int ak = a[k];
    152.             if (ak < pivot1) { // Move a[k] to left part
    153.                 a[k] = a[less];
    154.                 /*
    155.                  * Here and below we use "a[i] = b; i++;" instead
    156.                  * of "a[i++] = b;" due to performance issue.
    157.                  */
    158.                 a[less] = ak;
    159.                 ++less;
    160.             } else if (ak > pivot2) { // Move a[k] to right part
    161.                 while (a[great] > pivot2) {
    162.                     if (great-- == k) {
    163.                         break outer;
    164.                     }
    165.                 }
    166.                 if (a[great] < pivot1) { // a[great] <= pivot2
    167.                     a[k] = a[less];
    168.                     a[less] = a[great];
    169.                     ++less;
    170.                 } else { // pivot1 <= a[great] <= pivot2
    171.                     a[k] = a[great];
    172.                 }
    173.                 /*
    174.                  * Here and below we use "a[i] = b; i--;" instead
    175.                  * of "a[i--] = b;" due to performance issue.
    176.                  */
    177.                 a[great] = ak;
    178.                 --great;
    179.             }
    180.         }
    182.         // Swap pivots into their final positions
    183.         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    184.         a[right] = a[great + 1]; a[great + 1] = pivot2;
    186.         // Sort left and right parts recursively, excluding known pivots
    187.         sort(a, left, less - 2, leftmost);
    188.         sort(a, great + 2, right, false);
    190.         /*
    191.          * If center part is too large (comprises > 4/7 of the array),
    192.          * swap internal pivot values to ends.
    193.          */
    194.         if (less < e1 && e5 < great) {
    195.             /*
    196.              * Skip elements, which are equal to pivot values.
    197.              */
    198.             while (a[less] == pivot1) {
    199.                 ++less;
    200.             }
    202.             while (a[great] == pivot2) {
    203.                 --great;
    204.             }
    206.             /*
    207.              * Partitioning:
    208.              *
    209.              *   left part         center part                  right part
    210.              * +----------------------------------------------------------+
    211.              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
    212.              * +----------------------------------------------------------+
    213.              *              ^                        ^       ^
    214.              *              |                        |       |
    215.              *             less                      k     great
    216.              *
    217.              * Invariants:
    218.              *
    219.              *              all in (*,  less) == pivot1
    220.              *     pivot1 < all in [less,  k)  < pivot2
    221.              *              all in (great, *) == pivot2
    222.              *
    223.              * Pointer k is the first index of ?-part.
    224.              */
    225.             outer:
    226.             for (int k = less - 1; ++k <= great; ) {
    227.                 int ak = a[k];
    228.                 if (ak == pivot1) { // Move a[k] to left part
    229.                     a[k] = a[less];
    230.                     a[less] = ak;
    231.                     ++less;
    232.                 } else if (ak == pivot2) { // Move a[k] to right part
    233.                     while (a[great] == pivot2) {
    234.                         if (great-- == k) {
    235.                             break outer;
    236.                         }
    237.                     }
    238.                     if (a[great] == pivot1) { // a[great] < pivot2
    239.                         a[k] = a[less];
    240.                         /*
    241.                          * Even though a[great] equals to pivot1, the
    242.                          * assignment a[less] = pivot1 may be incorrect,
    243.                          * if a[great] and pivot1 are floating-point zeros
    244.                          * of different signs. Therefore in float and
    245.                          * double sorting methods we have to use more
    246.                          * accurate assignment a[less] = a[great].
    247.                          */
    248.                         a[less] = pivot1;
    249.                         ++less;
    250.                     } else { // pivot1 < a[great] < pivot2
    251.                         a[k] = a[great];
    252.                     }
    253.                     a[great] = ak;
    254.                     --great;
    255.                 }
    256.             }
    257.         }
    259.         // Sort center part recursively
    260.         sort(a, less, great, false);
    262.     } else { // Partitioning with one pivot
    263.         /*
    264.          * Use the third of the five sorted elements as pivot.
    265.          * This value is inexpensive approximation of the median.
    266.          */
    267.         int pivot = a[e3];
    269.         /*
    270.          * Partitioning degenerates to the traditional 3-way
    271.          * (or "Dutch National Flag") schema:
    272.          *
    273.          *   left part    center part              right part
    274.          * +-------------------------------------------------+
    275.          * |  < pivot  |   == pivot   |     ?    |  > pivot  |
    276.          * +-------------------------------------------------+
    277.          *              ^              ^        ^
    278.          *              |              |        |
    279.          *             less            k      great
    280.          *
    281.          * Invariants:
    282.          *
    283.          *   all in (left, less)   < pivot
    284.          *   all in [less, k)     == pivot
    285.          *   all in (great, right) > pivot
    286.          *
    287.          * Pointer k is the first index of ?-part.
    288.          */
    289.         for (int k = less; k <= great; ++k) {
    290.             if (a[k] == pivot) {
    291.                 continue;
    292.             }
    293.             int ak = a[k];
    294.             if (ak < pivot) { // Move a[k] to left part
    295.                 a[k] = a[less];
    296.                 a[less] = ak;
    297.                 ++less;
    298.             } else { // a[k] > pivot - Move a[k] to right part
    299.                 while (a[great] > pivot) {
    300.                     --great;
    301.                 }
    302.                 if (a[great] < pivot) { // a[great] <= pivot
    303.                     a[k] = a[less];
    304.                     a[less] = a[great];
    305.                     ++less;
    306.                 } else { // a[great] == pivot
    307.                     /*
    308.                      * Even though a[great] equals to pivot, the
    309.                      * assignment a[k] = pivot may be incorrect,
    310.                      * if a[great] and pivot are floating-point
    311.                      * zeros of different signs. Therefore in float
    312.                      * and double sorting methods we have to use
    313.                      * more accurate assignment a[k] = a[great].
    314.                      */
    315.                     a[k] = pivot;
    316.                 }
    317.                 a[great] = ak;
    318.                 --great;
    319.             }
    320.         }
    322.         /*
    323.          * Sort left and right parts recursively.
    324.          * All elements from center part are equal
    325.          * and, therefore, already sorted.
    326.          */
    327.         sort(a, left, less - 1, leftmost);
    328.         sort(a, great + 1, right, false);
    329.     }