JDK源码——Arrays.sort()的实现
主要分为两种，一个是对基本数据类型数组的排序实现，一个是对对象类型数组的排序实现。对于基本数据类型数组的排序实现主要采用了插入排序、快速排序和归并排序相结合的排序方法，对象类型数组的排序主要采用了归并排序和插入排序相结合的方法。每种排序方法都进行了一定的改进。今天分析的主要是基本数据类型元素的排序实现，各种基本数据类型排序的实现大同小异，这里采取对Int[]排序的实现代码进行分析。 进入Arrays.sort(int[] a)
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}可见，Arrays并没有自己来实现排序，而是委托给了DualPivotQuicksort类。进入上边的sort方法
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}首先对数组长度进行了判断，如果小于这个阈值（默认是286），直接选择快速排序进行排序。 如果大于这个阈值呢？咱接着往下看
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;
}
}进入了一个for循环，这个循环就是用来判断这个长数组是否基本有序，如果基本有序则选择归并排序，否则任然选择快排。如果它选择了快排，那么就会在这个for循环中的两个return处结束这次排序，如果选择了归并排序，则故事就在for循环之后继续发生（for循环之后的代码就是归并排序的实现）。
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;
}
//如果a中子序列个数是奇数，则最后一个没有完成配对归并的序列直接复制到b中
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;
}这个for循环是归并排序的主要部分，因为在上个for循环判断数组是否基本有序的时候，已经记录了原数组的各个有序的子序列，归并排序也就是对这些子序列进行自底向上的归并排序。 当然了如果选择了快排，快排的实现也进行了改进
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.
* 跳过最长的上升序列，比如数组a内容为：1245986，进过这步之后a[left]的内容将成为9,即Left=4 */
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循环第三个条件为什么是k=++left,这样a1和a2岂不是一个元素了嘛？
* 仔细一看红了脸，害羞.jpf
*/
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];
//保证a1>=a2
if (a1 < a2) {
a2 = a1; a1 = a[left];
}
//将a1进行插入
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;
//将a2进行插入
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;
}进入快排就一定快排吗？那是不可能滴！首先还是进行数组长度的判断，如果小于一定阈值(默认是47)，则进行插入排序，大家仔细看一下上边的代码，跟我们平常的插入排序有所不同，他每个轮次会完成两个元素的插入，官方称这种为pair insertion sort。 如果数组没这么小，那就会进行真正的快排了。这个快排被称为双轴快速排序，主要还是快排的思想，以及三项切分快速排序的升华。采用两个轴进行快排，使得整个数组分为三个部分，左边部分的元素都小于第一个轴，中间的部分大于等于第一个轴小于等于第二个轴，右边部分都大于第二个轴。然后对这三个部分递归调用双轴快排，当然还有许多细节的优化，比如如果中间部分过大则会把和轴相等的元素移动到两边，如果重复元素过多还会考虑三项切分快速排序等。
结语：这篇文没有细讲库函数的实现，而是给了一个大体的思路，为的就是把源码的味道留给大家自己去品尝，这里有一份提供了一些注释的源码文档，有什么想法我们可以一起讨论。