Java的List.sort()排序方法源码理解
排序的入口：List.sort()
按照常识，List是一个接口，照理说sort()是不会实现的。JDK8新增了default关键字来修饰接口里的方法，将方法标识为默认方法，对应的实现：
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
借用了Arrays.sort()的方法，那么Arrays.sort()又是怎么实现的呢？
二、第一层实现：Arrays.sort()
public static void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
这里可以看到一个判断分支if (LegacyMergeSort.userRequested)，如果为true，使用归并排序，否则使用TimSort。userRequested的值是用下面的代码取得的，允许用户通过参数手动选择是否使用归并排序：
userRequested = java.security.AccessController.doPrivileged(new sun.security.action.GetBooleanAction(“java.util.Arrays.useLegacyMergeSort”)).booleanValue();
我们先看看归并排序的实现。注意这段代码上方有段注释：未来的发行版中会被移除，也就意味着后续不会再使用归并排序了。
private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
T[] aux = a.clone();
if (c==null)
mergeSort(aux, a, 0, a.length, 0);
else
mergeSort(aux, a, 0, a.length, 0, c);
}
这两个mergeSort的区别只在于是否使用传入的Comparator。如果不使用，则使用Object.equals()的默认比较方式来进行排序。下面先深入看一下mergeSort的实现。
三、第二层实现之mergeSort
归并排序的思想是：
将数组拆分成两部分，分别对这两部分进行递归的归并排序。
排序完成后，同时用两个迭代器/指针遍历两个数组，依次将其中最符合要求的（从小到大排序就是最小的，从大到小排序就是最大的）放入新数组中。
如果一个数组的元素放完了，就把另一个数组剩余所有元素按已有顺序全部放入新数组中。
3.1 为什么选择归并排序？
在众多的常见比较排序算法中，在以空间换时间的策略下，归并排序有着最好的平均性能，并且是稳定的。这句话怎么理解呢？
比较排序，即通过比较来决定元素的顺序。
常见的比较排序，包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。
空间换时间，是指归并排序需要额外的临时数组，空间复杂度为O(n)
最好的平均性能，也是O(nlogn)，不会像快速排序在最差情况下的O(n^)
稳定的，是指排序后，相同大小的元素前后顺序不会改变。平均性能为O(nlogn)的堆排序和快速排序都是不稳定的。
各种常见排序算法的比较和原理本文就不展开讲了，网络上连篇累牍非常多，有兴趣可以自行了解。
3.2 归并排序源码解读
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
这个算法分两部分：
当数组长度<INSERTIONSORT_THRESHOLD(源码中是7)时，直接使用插入排序，用一部分时间复杂度上升换取一部分空间复杂度的下降。
对于归并排序的递归部分：
off表示偏移量，这个参数只有在数组内部分元素排序时才是一个非0值，整个数组排序时是0，可以不关心。
high表示传入的是数组长度，因此数组最后一个元素的下标是(high-1)。low则是第一个元素的下标。
计算中值使用了位操作。当长度为大于1的奇数时，均分的两个子数组，由于舍去了小数值，前一个数组的元素比后一个少一个。
对于归并排序的归并部分：
如果前一个数组的最后一个元素比后一个数组的第一个元素(大/小)直接合并，这里的System.arraycopy是native方法。
归并的遍历，简化了写法，没有先做下标的运算再调用System.arraycopy，而是直接两个数组一起遍历。可以看出此处for循环中的if是合并了很多场景写成的。
四、第二层实现之TimSort
4.1 背景
看完归并排序的实现，才是重头：TimSort。以下摘自JDK注释：
A stable, adaptive, iterative mergesort that requires far fewer than nlg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.
简单概括一下：TimSort是稳定、自适应、迭代的归并排序，在部分有序的数组上比较次数远少于nlogn，在随机数组上的表现和传统的归并排序一样。
TimSort的理论最初在1993年由Peter Mcllroy提出，由Tim Peters于2002年在Python中应用，后续逐步成为了包括Java、Swift、谷歌浏览器的默认排序方法。Tim Peters 本人对 TimSort 原理的介绍见：http://svn.python.org/projects/python/trunk/Objects/listsort.txt
4.2 基本概念
不打算在这里介绍过多的概念，造成阅读代码时的困难，先知道一些核心的概念就行了。
run —— 可以直观地翻译为一趟跑步的距离、旅程、航程等，代表了一部分已经有序的子数组。这里不打算自己造概念，以下仍称为run。
galloping mode —— 可以译为加速模式，同样不翻译。
4.3 算法框架
先不纠结具体细节，看一下TimSort的整体框架。注意在Arrays.sort()调用处的入参是TimSort.sort(a, 0, a.length, c, null, 0, 0)，其中a是待排序数组T[] a, c是比较器Comparator<? super T> c。
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
// (1)第一部分
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
//(2)
/**
* 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<T> 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);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
先看最开头的部分(1)。如果待排序部分nRemaining过小(为0或1)，直接返回结果，很好理解。
如果nRemaining<MIN_MERGE(MIN_MERGE被设置为32)，则使用一个“微型”的TimSort，也即二分插入排序的变体。这个二分插入排序内部不做任何合并。这一步的解读参考后文5.1节，这里暂时跳过，只需要知道countRunAndMakeAscending方法的目的是计算待排序部分__从起始位置起，保持升序或降序的最长的run的长度initRunLen__。
接着看第(2)部分。这部分先创建了一个TimSort对象，对象内有什么先不管，继续看框架部分。
int minRun = minRunLength(nRemaining)是一个纯粹对数值计算方法，目的是计算出将数组需要划分成多少个run，这时的run的长度使用minRun表示，并且需要让nRemaining/minRun最接近一个2的幂（实际上nRemaining/k严格小于2的幂）。这种情况下的分组的个数接近2的幂，更利于合并。具体的计算方法minRunLength()不在这节展开，请参考后文5.2节。
计算出要拆分的run的个数minRun后，进入循环，循环中包括：
计算数组中从lo开始最长连续递增的序列长度
如果长度不满一个minRun，强制将从lo开始的数组扩展到minRun长度或在排序中可以处理的最大长度nRemaining。
将当前处理的run压栈pushRun并视情况mergemergeCollapse，并将lo下标前移，未排序个数nRemaining减去本次的runLen
循环直到nRemaining==0。
循环完成时，做一次强制merge——mergeForceCollapse
更具体的实现，接下来需要研究一下TimSort这个类使用的三个类方法pushRun、mergeCollapse、mergeForceCollapse。
4.4 TimSort类的实例化
TimSort类只会在调用TimSort.sort()方法时实例化一次，并且这个构造方法是private的。借助这个对象实例，保存一些处理中数据。
4.4.1 成员变量
简单翻译了一下注释。如果看不懂，可以先不纠结，继续看后续的排序方法来理解。
/**
* 最小的待合并的run长度的阈值
*/
private static final int MIN_MERGE = 32;
/**
* 待排序的数组
*/
private final T[] a;
/**
* 比较器
*/
private final Comparator<? super T> c;
/**
* galloping mode 的初始阈值。连续取胜达到该次数后切换到 gallop
*/
private static final int MIN_GALLOP = 7;
/**
* 当前进入 galloping mode 的阈值，随数据特征动态调整
*/
private int minGallop = MIN_GALLOP;
/**
* 初始化用于存放临时排序数据的数组长度最大值
*/
private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
/**
* 用于归并的临时数组
*/
private T[] tmp;
private int tmpBase; // base of tmp array slice
private int tmpLen; // length of tmp array slice
/**
* 待归并的run的栈。第i个run下标从base[i]开始，长度是len[i]。
* 满足runBase[i] + runLen[i] == runBase[i + 1]
*
*/
private int stackSize = 0; // Number of pending runs on stack
private final int[] runBase;
private final int[] runLen;
4.4.2 构造方法
排序时创建的参数是work=null的，因此不会走下面的分支。
构造方法初始化了用于存放临时数据的数组，以及用来存放待排序栈的run的起始下标和长度。
private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) {
this.a = a;
this.c = c;
// Allocate temp storage (which may be increased later if necessary)
int len = a.length;
int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
if (work == null || workLen < tlen || workBase + tlen > work.length) {
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
T[] newArray = (T[])java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), tlen);
tmp = newArray;
tmpBase = 0;
tmpLen = tlen;
}
else {
tmp = work;
tmpBase = workBase;
tmpLen = workLen;
}
/*
* Allocate runs-to-be-merged stack (which cannot be expanded). The
* stack length requirements are described in listsort.txt. The C
* version always uses the same stack length (85), but this was
* measured to be too expensive when sorting "mid-sized" arrays (e.g.,
* 100 elements) in Java. Therefore, we use smaller (but sufficiently
* large) stack lengths for smaller arrays. The "magic numbers" in the
* computation below must be changed if MIN_MERGE is decreased. See
* the MIN_MERGE declaration above for more information.
* The maximum value of 49 allows for an array up to length
* Integer.MAX_VALUE-4, if array is filled by the worst case stack size
* increasing scenario. More explanations are given in section 4 of:
* http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf
*/
int stackLen = (len < 120 ? 5 :
len < 1542 ? 10 :
len < 119151 ? 24 : 49);
runBase = new int[stackLen];
runLen = new int[stackLen];
}
4.4.3 排序过程
4.4.3.1 run栈的处理
首先看下怎么处理存放各个run的栈的。
压栈方法pushRun，将当前处理的run放入栈中：
private void pushRun(int runBase, int runLen) {
this.runBase[stackSize] = runBase;
this.runLen[stackSize] = runLen;
stackSize++;
}
压栈后，会对当前的run栈立刻判断是否需要归并，并做合并mergeCollapse()，全部run处理完后，再调用mergeForceCollapse()合并全部的run。
先不管判断分支的含义，看下整体的结构：
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
}
}
}
看下这段逻辑的含义：
调用该方法时，n>=0。
当n>=1时，栈中至少3个run。这时检查第n-1个是否比后两个长度小。如果是，再判断n-1是否比n+1长度小，如果仍然是，那么处理n-1这个栈，即mergeAt(n)；否则，处理n这个栈；
当n>=1，但是第n-1个比n和n+1的长度都长时，处理第n个；
n=0，即只有两个栈时，处理第0个run，即mergeAt(n)；
其他情况忽略，本次不合并栈。
private void mergeForceCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
}
}
对于最后一次合并，类似的，如果n-1的长度小于n+1，就合并n-1这个run。其他情况合并第n个
直到整个栈清空。
鲲鹏昇腾开发者社区是面向全社会开放的“联接全球计算开发者，聚合华为+生态”的社区，内容涵盖鲲鹏、昇腾资源，帮助开发者快速获取所需的知识、经验、软件、工具、算力，支撑开发者易学、好用、成功，成为核心开发者。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)