上一篇谈到的双轴快排，是Arrays对八种基本类型进行排序的算法，针对其它的对象类型，JDK1.6及以前的版本使用的是归并排序，从JDK1.7开始，默认情况下会采用Timsort排序算法，而Collections.sort实际上也是调用Arrays.sort方法。现实中的大多数据通常是有部分已经排好序的，该算法利用这一特点提升了排序效率，下面将跟随JDK1.8源码，对Timsort的实现进行分析。
排序的核心代码从TimSort.sort方法开始，首先判断需要排序的元素个数，如果小于一个阈值(在Tim的C语言实现中默认为64，JDK中为32)，先找出从起点位置开始的最大升序或严格降序列长度，并对降序列进行翻转，然后进行二分插入排序。
// If array is small, do a “mini-TimSort” with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// Binary insertion sort
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
如果长度大于这个阈值，开始从左往右遍历数组，找出一个升序列或严格降序列，同样需要对降序列进行翻转，得到的序列这里称为一个run。如果这个run的长度太小，用二分插入排序进行增补，再入栈并尝试合并，然后继续往右寻找下一个run。
/
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
每次有新的run入栈，都会对栈里相邻的两个run按照一定规则尝试进行合并，使得对于任意相邻的三个run，它们的长度X、Y、Z满足两个条件：
X > Y + Z
Y > Z
具体做法是，从栈顶的三个run开始判断，如果没有同时满足两个条件，就通过合并把两个run变为一个更大的run，然后继续循环对栈顶三个run进行判断。
/
* Examines the stack of runs waiting to be merged and merges adjacent runs
* until the stack invariants are reestablished:
*
* 1. runLen[i – 3] > runLen[i – 2] + runLen[i – 1]
* 2. runLen[i – 2] > runLen[i – 1]
*
* This method is called each time a new run is pushed onto the stack,
* so the invariants are guaranteed to hold for i < stackSize upon
* entry to the method.
*/
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize – 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n – 1] < runLen[n + 1])
n–;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}
为了提高效率，在合并两个相邻run的时候，采用了一个叫Galloping的模型进行优化。例如现在要合并较小的A和较大的B两个run，因为A和B已经分别是排好序的，用二分查找找到B的第一个元素在A中何处插入，找到以后，A在该素左边的部分就不需要比较了。同样，找到A的最后一个元素在B的何处插入，B在该元素之后的元素也不需要比较了。
/*
* Find where the first element of run2 goes in run1. Prior elements
* in run1 can be ignored (because they’re already in place).
*/
int k = gallopRight(a[base2], a, base1, len1, 0, c);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0)
return;
/*
* Find where the last element of run1 goes in run2. Subsequent elements
* in run2 can be ignored (because they’re already in place).
*/
len2 = gallopLeft(a[base1 + len1 – 1], a, base2, len2, len2 – 1, c);
assert len2 >= 0;
if (len2 == 0)
return;
接下来合并中间的部分，用一个临时存储空间，大小是待合并的两部分中较小的部分的大小。先将较小的部分复制到这个临时存储空间，然后用原先存储这2个部分的空间来存储合并后的元素。剩下就是简单归并排序：依次从左到右或从右到左，不断比较两个序列的第一个元素并插入到相应位置。
// Merge remaining runs, using tmp array with min(len1, len2) elements
if (len1 <= len2)
mergeLo(base1, len1, base2, len2);
else
mergeHi(base1, len1, base2, len2);
总结：Timsort结合了归并排序和插入排序，很好地利用了无序数列中有序的部分，按照升序和降序子序列进行分区，减少了升序部分的回溯和降序部分的性能倒退。Galloping模型的引入也降低了不必要的比较次数，大大优化了两个相邻run的合并效率。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/203324.html原文链接：https://javaforall.net
