概述：
JDK提供了概述：
JDK提供了对于数组排序的库函数，java.util.Arrays类中的一些列重载的sort的方法为给定数组进行排序，以下是各个重载方法签名：
void sort (char[])
void sort (char[], int, int)
void sort (byte[])
void sort (byte[], int, int)
void sort (T[], Comparator)
void sort (short[], int, int)
void sort (short)
void sort (double[], int, int)
void sort (Object[])
void sort (Object[], int, int)
void sort (T[], int, int, Comparator)
void sort (double[])
void sort (float[], int, int)
void sort (float[])
void sort (int[], int, int)
void sort (long[])
void sort (long[], int, int)
void sort (long[])
对于这些sort方法，我们可以从不同的角度分类：
根据第一个参数的类型，可以将这些方法分为3类：基本数据类型数组的数值排序方法，提供了对于byte，short，int，long，char，float，double这些基本数据类型的数组的排序方法；自定义类的对象数组排序方法。提供了对于任意类类型个数组的排序方法，这些方法的输入参数为Object数组；泛型方法提供了泛型对象数组的排序实现。 根据参数的个数，可以将这些方法分为3类：包含1个参数的方法对整个数组排序，包含3个参数的方法对数组的一部分进行排序，后两个参数确定了数组中要排序元素的范围；泛型方法中包含比较元素大小时使用的比较器类。 根据实现的原理，可以将这些方法分为2类：数据数组排序方法采用一种结合了归并排序、插入排序、改进后的快速排序算法来实现，这些方法提供了以上7种基本数据类型的数组的排序；对象数组排序方法则。。。。。。。。。，这些方法提供了对象数组和泛型数组的排序算法的实现。
下文的讨论基于最后一种分类角度进行。本文首先来分析数据数组排序方法的实现。
数据数组排序方法：
·代码：
据数组排序方法提供了byte，short，int，long，char，float，double 这7种基本数据类型的数组的排序实现。下面以int数组排序方法的实现为例，分析程序排序机理。
以下为int数组对应的sort方法的代码实现：
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
方法实现很简单，直接调用DualPivotQuicksort类中的sort方法实现排序，该方法代码如下：
/**
* Sorts the specified range of the array using the given
* workspace array slice if possible for merging
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param work a workspace array (slice)
* @param workBase origin of usable space in work array
* @param workLen usable size of work array
*/
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
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 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;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
int[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new int[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}
// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}
以上代码对于归并排序和快速排序进行了改进，然后将这两种改进的算法结合起来，实现数组的排序，下文中，笔者首先介绍归并排序的改进，然后介绍快速排序的改进算法。
·对于归并排序的改进：
以上方法对给定数组的指定区间内的数据进行排序，同时允许调用者提供用于归并排序的辅助空间。实现思路为：首先检查数组的大小，如果数组比较小，则直接调用改进后的快速排序完成排序(这个改进的快速排序我们在后面介绍)，如果数组较大，则评估数组的无序程度，如果这个数组几乎是无序的，那么同样调用改进后的快速排序算法排序；如果数组基本有序，那么采用归并排序算法对数组进行排序。
根据这样的思路，整个代码实现可以分为3个部分：
·第一部分
代码的 15-18 行为第一部分，这一部分检查了数组的大小，如果数组大小小于QUICKSORT_THRESHOLD的值，则程序认为数组很小，可以直接调用改进快排实现排序。常量QUICKSORT_THRESHOLD的值程序定义为286。
· 第二部分：
代码的 20-61行为第二部分，该部分对于数组的无序程度进行了评估。评估的基于这样的思路：对于任意的数组，我们总是可以将其分割成若干个递增或递减的子数组(或者说：拆分成若干个“单调”的子数组)，例如：序列 {9, 5, 2, 7, 8, 3, 4} 可以拆分为3个单调子数组：{9， 5， 2}、{7， 8}、{3， 4}， 其中每一个子数组都是单调的，不是递增，就是递减。
程序定义run数组来存储每一个子数组的开始下标，该部分的for循环体对于递增、递减、相等的子序列进行了处理，29、30行的if分句判定了递增子序列；31-35行的else if分句处理的递减序列，同时将递减序列转化为递增序列；36-43的else分句处理了相等的序列。下图描述了run数组和待排序a数组的关系：
image
需要说明的是，30行和32行的while循环的第2个条件都包含了等于，因此，只有前面的 if 和 else if的情况都不成立时，后面的else分句才会执行，例如：序列{1， 2， 3， 3， 3， 3}，以及{3， 2， 1， 1， 1}划分后仅为1个子序列，就是它本身；而序列{1， 2， 3， 2， 2， 2}则会被划分成2个子序列：{1， 2， 3} 和 {2， 2， 2}。
45-52行给出了评估数组无序程度的指标，即考察划分出的子序列的个数，即run数组的大小，如果run数组元素个数大于常量 MAX_RUN_COUNT， 那么认为整个数组基本上是无序的，此时调用改进的快排算法排序，后面的代码不再执行；否则，程序认为整个数组基本上是有序的，继续执行下面的代码，利用归并排序算法完成排序。常量程序MAX_RUN_COUNT定义其值为67。
55-58行给run数组的末尾添加了一个“哨兵”元素，这个元素的值为right+1，代表一个空的子序列。这里又分为两种情况：如果原数组在划分后最后一个元素独自为一个子序列，那么在27-43行的循环执行完毕后，run数组的最后一个元素的值为right，此时须有再添加一个代表空序列的哨兵元素；如果划分后，原数组中的最后一个元素并不是独自为一个子序列，那么27-43行的循环执行完毕后，run数组的最后一个元素的值就是right+1，此时run数组的最后一个元素已经是哨兵，就不需要再添加了。
程序执行到这里，意味着程序认为数组基本上是有序的，采用归并排序算法进行排序，这个哨兵元素的作用在第三部分的代码中会有体现，这里略过。
59-61行给出了另一种特殊情况，即整个数组划分后就只有1个单调子序列，那么说明数组本身就是有序的，不需要再执行其他操作，程序结束。
最后，笔者感到困惑的地方是：36-42行关于相等序列的处理，程序判定，如果相等序列的长度不小于MAX_RUN_LENGTH，那么就直接调用改进快排来处理。这里的常量MAX_RUN_LENGTH的值是33，是一个很小的数字，笔者暂时不了解此设定的用意!
· 第三部分：
63-109行为本程序的第三部分，该部分程序对划分好的数据进行了二路归并排序。排序过程中用到了随参数传入的辅助空间work。
63-85行是一个初始化的操作，该操作的意义我们在后面说明，首先看87-108行的代码，这里是归并排序的主体，循环的每一轮迭代都将数组a中的两个相邻的单调子序列“归并”为一个新的单调子序列，存储在数组b中。89行开始的内层的for循环成对地归并数组a中的单调子序列，如下图：
image
循环中的每轮迭代将两个相邻的单调子序列进行归并，第一个子序列的范围是run[k-2] - run[i-1], 第二个子序列的范围是run[k-1] - run[k]，内层循环每次迭代都将k增加2。同时last变量记录了归并得到的新的子序列的个数，同时更新run数组的内容。
但是，这里有一个问题，如果a数组中的子序列个数是奇数，那么最后一个子序列就无法进行配对、归并操作，此时，直接将这个子序列复制到b中。 代码是100-105行完成了这个工作。
显然，每轮迭代以后，子序列的数目都会减少，因此，反复地进行迭代归并后，最终会使得整个数组只包含1个单调递增的子序列，此时整个数组排序完成。因此，每轮迭代后，交换a、b指针，继续执行下一轮迭代时，同样对a数组进行归并，存储在b数组中。就这样，利用a和b代表的存储空间仿佛地进行归并，就可以完成数组的排序。106-107行的代码完成了交换a和b指针的工作。
这里也就解释了67-85行代码的意义，初始情况下，a和b指针一定1个指向原数组，另一个指向辅助空间。下面的if语句则根据需要的迭代次数对a和b指针的指向进行指定，确保在迭代归并结束以后，排好序的数组依旧在调用函数之前的存储空间内。这里的代码还检查了辅助空间的大小是否足够，如果不够，则重新申请内存。
最后，对于89行的循环还有一个问题，当处理a数组的最后一对单调子序列的归并操作时，此时，hi的值已经超出了run数组的大小，即k值已经越界，为了避免这种情况的发生，我们在run数组的末尾添加了一个“哨兵”元素，这样就保证了在循环过程中不会发生数组越界的异常。代码的55-61行、98行、以及104行完成了添加哨兵元素的工作。
以上是本函数对于归并排序的改进算法。
·对于快速排序的改进：
以上的代码的16、39、50行调用了DualPivotQuicksort类中的另一个排序方法，该方法的实现机理是基于对于传统快速排序的改进，该方法在数据无序程度较严重时被调用，代码如下：
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param leftmost indicates if this part is the leftmost in the range
*/
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
// 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;
}
// 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;
// Sort these elements using insertion sort
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
}
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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];
/*
* The first and the last elements to be sorted are moved to the
* locations formerly occupied by the pivots. When partitioning
* is complete, the pivots are swapped back into their final
* positions, and excluded from subsequent sorting.
*/
a[e2] = a[left];
a[e4] = a[right];
/*
* Skip elements, which are less or greater than pivot values.
*/
while (a[++less] < pivot1);
while (a[--great] > pivot2);
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of ?-part.
*/
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
a[k] = a[less];
/*
* Here and below we use "a[i] = b; i++;" instead
* of "a[i++] = b;" due to performance issue.
*/
a[less] = ak;
++less;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] < pivot1) { // a[great] <= pivot2
a[k] = a[less];
a[less] = a[great];
++less;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
/*
* Here and below we use "a[i] = b; i--;" instead
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
--great;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
/*
* If center part is too large (comprises > 4/7 of the array),
* swap internal pivot values to ends.
*/
if (less < e1 && e5 < great) {
/*
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
++less;
}
while (a[great] == pivot2) {
--great;
}
/*
* Partitioning:
*
* left part center part right part
* +----------------------------------------------------------+
* | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
* +----------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (*, less) == pivot1
* pivot1 < all in [less, k) < pivot2
* all in (great, *) == pivot2
*
* Pointer k is the first index of ?-part.
*/
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak == pivot1) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else if (ak == pivot2) { // Move a[k] to right part
while (a[great] == pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] == pivot1) { // a[great] < pivot2
a[k] = a[less];
/*
* Even though a[great] equals to pivot1, the
* assignment a[less] = pivot1 may be incorrect,
* if a[great] and pivot1 are floating-point zeros
* of different signs. Therefore in float and
* double sorting methods we have to use more
* accurate assignment a[less] = a[great].
*/
a[less] = pivot1;
++less;
} else { // pivot1 < a[great] < pivot2
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
}
// Sort center part recursively
sort(a, less, great, false);
} else { // Partitioning with one pivot
/*
* Use the third of the five sorted elements as pivot.
* This value is inexpensive approximation of the median.
*/
int pivot = a[e3];
/*
* Partitioning degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +-------------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +-------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of ?-part.
*/
for (int k = less; k <= great; ++k) {
if (a[k] == pivot) {
continue;
}
int ak = a[k];
if (ak < pivot) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else { // a[k] > pivot - Move a[k] to right part
while (a[great] > pivot) {
--great;
}
if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
++less;
} else { // a[great] == pivot
/*
* Even though a[great] equals to pivot, the
* assignment a[k] = pivot may be incorrect,
* if a[great] and pivot are floating-point
* zeros of different signs. Therefore in float
* and double sorting methods we have to use
* more accurate assignment a[k] = a[great].
*/
a[k] = pivot;
}
a[great] = ak;
--great;
}
}
/*
* Sort left and right parts recursively.
* All elements from center part are equal
* and, therefore, already sorted.
*/
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
}
}
该算法的实现了一种称为“DualPivotQuicksort”的排序算法，中文可以翻译为“双枢轴快速排序”，可以看作是经典快速排序算法的变体。算法的基本思路是：如果数组的数据量较少，则执行插入排序就可以达到很好的效果，如果数据量较大，那么确定数组的5个分位点，选择一个或两个分位点作为“枢轴”，然后根据快速排序的思想进行排序。
根据算法的思路，以上代码也可以划分为三个部分：
第一部分：
12-72行为第一部分，该部分对数组进行插入排序。对于何时执行插入排序，程序定义了常量INSERTION _SORT_THRESHOLD，如果数组长度小于这个常量，程序认为这是一个小规模的数组，采用插入排序算法进行处理，后面的代码不再执行；否则，程序执行快速排序算法处理。这里的常量INSERTION _SORT_THRESHOLD程序定义其值为47。
这一部分对于插入排序也给出了一种改进的方案，基本思路是每次迭代过程中同时完成两个元素的插入排序，代码的注释给出了该算法的名称—— pair insertion sort，中文可以译为“双插入排序”。代码中第15-29行为经典插入排序算法的实现，32-70行为双插入排序算法的实现。下面简要说明双插入排序算法的思路。
48-63行的循环代码中用a1和a2两个变量存储每次迭代时要完成排序的两个相邻的元素。首先确保a1和a2的大小关系是a1≥a2。然后利用变量k遍历a1和a2之前的元素，找到第一个小于a1的元素的位置，确定a1的位置，54-57行的while循环完成了这一步骤；由于a2≤a1，所以a2的位置一定在a1之前，因此，确定了a1的位置后，k继续遍历，此时的步骤和普通的插入排序是完全相同的，59-62行的代码完成了这一步骤。
对于双插入排序，有一种特殊情况，如果原数组的元素格式是奇数的话，那么最后一个元素就没有元素与其配对完成插入排序，因此，还需要额外进行一次插入排序来完成排序，这里的处理步骤和经典插入排序也和经典插入排序是完全相同的，65-79行的代码完成了这个处理过程。
另外，为了提高算法效率，在算法开始前，我们可以跳过数组前面已经有序的部分，从第一个无序的元素开始遍历、插入，31-38行的代码完成了这个初始化过程。
需要注意的是，48-63行的代码中，对于变量k的值没有进行数组边界检查，根据给出的代码注释，现有的程序设计思路下，即使不对k变量进行数组越界的检查，也一定不会发生异常。这里的具体原因会在下文中说明，这里先略过。
第二部分：
74-108行为代码的第二部分。如果数组比较大，那么就要采用快速排序的算法来处理。本部分程序对于快速排序算法的进行确定了分位点。分为点的确定思路是将数组长度划分为7等份，然后确定5个分割点为3/14分位点、5/14分位点、中点、9/14分位点以及11/14分位点，程序中分别记为：e1、e2、e3、e4、e5。分为点的确定方式如下图：
image
确定分位点后， 90-107行代码，对于5个分位点的元素进行了排序。
以上为第二部分的代码，逻辑比较简单。
第三部分：
109-336行为第三部分，本部分是这个方法的主体，也是快速排序算法的实现，以下为具体的实现思路。
第三部分的算法实现又可以分为两种情况：
情况一：
如果前面得到的5个分位点的值各不相同，那么就选择e2和e4分为点作为快速排序的“枢轴”，采用双枢轴快速排序算法进行排序；否则，选择e3，作为枢轴，进行快速排序，这里虽然仅有一个枢轴点，但也和经典的快速排序算法有一定的区别。下文中首先介绍双枢轴快速排序的实现。
113-267行为双枢轴快速排序的实现，类似于经典的快速排序算法，每一轮递归的目的就是找到枢轴点pivot1 = e2 和 pivot2 = e4的正确位置，当本轮递归结束时，连个枢轴点将整个数组划分为3个部分，元素大小小于pivot1的部分、元素大小介于pivot1和pivot2之间(包含边界)的部分以及元素大小大于pivot2的部分。如下图：
image
137-188行的while循环实现了这一过程，程序中用less变量记录第一部分的边界，great变量记录第3部分的边界，循环变量k可指示了本轮迭代中待检查的元素，此时，基于less和k之间的元素就是第二部分的元素，基于k和great之间的元素则尚未检查，如下图：
image
根据当前检查元素a[k]的结果，又可以分为三种情况：
① 如果a[k]属于第二部分，此时，不需要做任何操作，直接进行下一轮循环即可。
② 如果a[k]属于第一部分，此时，第一部分需要扩张，由于和第一部分相邻的是第二部分，此时第二部分需要向右“平移”以扩大第一部分，平移的方法是将第二部分最左边的元素放置到最右边，然后将左边的空余位置中填入a[k]即可，如下图：
image
159-166行代码处理了以上过程。
③ 如果a[k]属于第三部分，则第三部分需要扩张，由于和第三部分相邻的是未知的部分，因此a[great]可能属于第二部分，也可能属于第一部分。这里程序首先取出a[great]元素，然后再确定a[great]的位置。
如果a[great]输入第二部分，那么直接将其放在a[k]的位置即可：
image
如果a[great]属于第一部分，此时需要扩张第一部分，同时将第二部分向右平移，处理方式和情况①类似，如下：
image
168-185行代码处理了以上过程。
为了提高算法效率，131-135行程序在迭代开始前对于数组进行了预处理，找出已经有序的第一部分和第三部分，迭代从第一个失序的元素开始。
程序在算法迭代开始前，先将两个枢轴值从数组中抽出，并将数组的首末元素插入到两个枢轴点的空余位置，然后开始迭代，迭代完成后，在将两个枢轴值插入到第一部分的末尾和第三部分的首部，就找到了两个枢轴值的正确位置。128行、129行代码将枢轴值从数组中取出，并将首末元素填入；190、191行代码将枢轴值重新插入到数组中。
找到枢轴值的正确位置后，接下来类似于经典快速排序，递归地调用本方法对枢轴值划分的3个部分进行排序。194、195行代码对于第一、第三部分进行了排序。而对于第二部分，程序做了一些优化，如下：
在某些情况下，枢轴值的取值可能距离数据的中心点较远，即，通过156-187行的迭代后，只有少部分数据落在了第一、第三部分，大部分数据依然留在第二部分，此时直接对第二部分排序效率可能较低，因此程序再次对于部分进行筛选，将第二部分又划分为3个子区间：等于pivot1的区间、介于pivot1和pivot2(不包含边界)的部分、等于pivot2的区间，划分完成后，只需要对第二子区间的数据进行递归调用方法排序即可。从某种程度上，这样的优化减少了第二部分参加递归调用的数据量。
197-264行代码实现了这一优化，代码的逻辑基本和前面137-187行的循环相同，这里不再赘述：
image
完成优化后，267行代码完成了对于中部区间序列的排序。
情况二：
上文中情况一为5个分位点个各不相同的处理情况，而对于5个分位点如果存在两个分位点的值相同，程序给出了另一种策略，此时不再使用双枢轴，而是仅选择 pivot = e3 分位点作为唯一的枢轴点，不同于经典快速排序算法的是，这种情况下，算法依旧将数组划分为三个部分：小于pivot的部分、等于pivot的部分以及大于pivot的部分。
276-327行代码给出了情况二的实现，代码逻辑基本和前面的137-187行的迭代代码相同，这里也不再赘述：
image
334、335行代码对于第一部分和第二部分通过递归调用方法进行排序，此时，不同于情况一，第二部分已经是有序的，因此不需要对第二部分优化，也不需要对第二部分再次递归调用方法。
最后还有一个小问题需要说明，那就是前面提到的40-70行代码双插入排序不需要检查k值数组越界的原因。通过观察可以发现，这部分代码只有在leftmost值为false的情况下，即待排序数据的范围的不是整个数组的最左边时，才会执行。观察代码2，可以发现调用到代码3方法的地方(代码2:13、39、50行),传入的foremost的值都是true，因此，如果程序执行到了40-70行的代码，此时该方法的调用者一定还是该方法本身(代码3：194、195、267、334、335行),而此时，如果传入的leftmost为false，那么可以保证整个数组的最小值一定不再这个区间内，因此插入排序过程中一定会在遍历到数组首部之前找到待插入元素的位置，也就一定不会出现数组越界的异常情况。
以上就是JDK中对于数据数组排序方法：Arrays.sort()的实现方式。
下面简单说一说笔者第一次阅读JDK源码遇到的问题和一些心得体会：
(1) 编代码加注释的重要性：JDK的源代码给出了很详尽的注释，这些注释对于笔者阅读代码过程中提供了很大的帮助。程序代码是给开发者阅读的，并不是给计算机，编码过程中添加一些注释有助于其他开发人员阅读和理解。
(2)JDK的编码风格：笔者认为，JDK源码的编码风格比较奇怪，例如：原本对于for循环，有一个不成文的规定是：循环头的三个部分最好是对一个变量进行操作，而通过阅读发现，JDK的源码中对于for循环有各种各样的风格，导致笔者感觉代码非常晦涩难懂。这种编码风格笔者个人不提倡。但是，这也充分表明代码的作者编程功力非常深厚，对于Java语法的应用可以说是如鱼得水、融会贯通。所以，相比这些大牛，我们需要学习的东西还有很多。
(3)代码2中37-42行代码：当数组中出现长度超过MAX_RUN_LENGTH == 33的等值序列时，就直接调用快速排序，这样设计的用意笔者依旧不明白。
(4)对于代码3中的第二部分划分分为点的代码，分为点选取的依据是什么？如果仅仅是为了双枢轴快速排序算法寻找枢轴点的话，直接选择两个三等分点作为枢轴点也是可以达到相同的效果的。分位点的选取依据笔者尚不明白。
(5)笔者认为代码3中的第三部分有些冗余，如果将159和167行代码中的判定条件中包含等于，那么当循环结束时，第二部分就已经优化完成，就不再需要213-265行的中部优化代码；如果将309行的判定条件也包含了等于，那么情况二的排序算法和经典的快速排序算法就完全相同了。之所以是现在的设计方式，笔者认为可能是为了尽可能减少参与递归调用处理的数据量，由于等值序列已经是有序序列，因此，将其从程序处理的数据中抽出不会改变程序的结果，但是程序处理的数据量会有减少，效率就会提高。但是笔者目前无法用更严密的方式证明这样的策略可以提高算法效率。
(6)代码3的策略选择问题，为何只有五个分位点各不相同时才能使用双枢轴快速排序算法，这样设计的用意是什么？笔者尚不明白。
(7)双枢轴快速排序算法相对于经典快排的优越性：根据代码中的注释，双枢轴快速排序算法由于经典快排，但是笔者目前无法给出准确的证明，关于这一点，还需要参考更多的资料。
网友评论