- 概述
- Collections.sort
- List.sort
- 总结
来看看Collections.sort与Arrrays.sort的排序算法，本文基于JDK1.8。
Collections.sort容器工具类Collections.sort提供了以下几种方式：
public static> void sort(List list) { list.sort(null); } public static void sort(List list, Comparator c) { list.sort(c); }
可以看到以上两个静态排序方法本质的排序算法其实是一样的(都调用了list.sort方法)，只是排序中比较的方法不同：
- 第一种排序方法，由于不用传入比较器，因此排序的List本身需要实现Comparable，实现接口中的compareTo方法用于比较；
- 第二种排序方法，需要传入比较器Comparator，借用比较器的compare方法来协助排序。
Collections.sort的排序交由List.sort实现
default void sort(Comparator c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
来看看Arrays.sort(T[] a, Comparator c)
public staticvoid sort(T[] a, Comparator c) { if (c == null) { sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); } }
不传入比较器时调用Arrays.sort(Object[] a)
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
这里LegacyMergeSort.userRequested是Arrays的内部来LegacyMergeSort的一个静态属性userRequested
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
这个系统参数值可通过
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
方式设置，即使用旧的归并排序算法legacyMergeSort：
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
//src 待排数组的副本，用于归并排序中间结果存放
//dest 真正要排序的数组，最后排完序后的也是该数组
//low 排序起始下标(包含)
//high 排序结束下标(不包含)
//off 偏移量，在这里始终为0
@SuppressWarnings({"unchecked", "rawtypes"})
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// 当待排元素个数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) //相当于 if (q >= high || (p < mid && ((Comparable)src[p]).compareTo(src[q])<=0))
//当q >= high 或 src[p] <= src[q]
dest[i] = src[p++];
else
//当p >= mid 或 src[p] > src[q]
dest[i] = src[q++];
}
}
可以看到以上归并排序算法是改进的归并排序，在待排元素数<7时，就用简单插入排序，否则采用归并排序。
当java.util.Arrays.useLegacyMergeSort=false时(默认)，调用ComparableTimSort.sort(Object[] a, int lo, int hi, Object[] work, int workbase, int workLen)
static void sort(Object[] a, int lo, int hi, Object[] work, int workbase, int workLen) {
//校验参数合法性
//assert 逻辑表达式;逻辑表达式结果若为true，断言通过，继续执行以下代码；否则，在打开虚拟机参数-ea条件下，抛出java.lang.AssertionError
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
//待排元素数
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) {
//获取数组a从下标lo开始已经有序的元素个数
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);//二分插入排序
return;
}
ComparableTimSort ts = new ComparableTimSort(a, work, workbase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) { //run不满足最短run长度时，二分插入扩展run
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse(); //高效率归并部分run
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse(); //强制归并所有的run
assert ts.stackSize == 1;
}
//获取a[lo] ~ a[hi-1]中从下标lo开始已经有序的元素个数
//反序也满足，若反序，会通过reverseRange方法逆置数组元素
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
assert lo < hi;
int runHi = lo + 1;
//若元素个数为1，则有序元素个数为1
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
//逆序
if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
//统计最左连续逆序的元素个数
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi); //因为是逆序，所以要逆置为有序
} else { // Ascending
//统计最左连续有序的元素个数
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
//逆置a[lo] ~ a[hi]
private static void reverseRange(Object[] a, int lo, int hi) {
hi--;
while (lo < hi) {
Object t = a[lo];
a[lo++] = a[hi];
a[hi--] = t;
}
}
//用二分插入排序算法对a[lo] ~ a[hi-1]进行排序，排序起始下标为start
private static void binarySort(Object[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) { //从start开旭排序
Comparable pivot = (Comparable) a[start]; //待排元素
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
//二分查找pivot应该插入的位置，最后left即为pivot最终在数组的下标
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
//需要向后移动的元素个数
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
//移动个数小时，直接移动数组元素，否则用arraycopy
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n); //将数组a从left开始的n个元素复制到left+1上
}
a[left] = pivot;
}
}
把上面sort方法中TimSort部分抽绎出来着重看：
static void sort(Object[] a, int lo, int hi, Object[] work, int workbase, int workLen) {
......
//上面是待排元素少时的二分插入排序
//下面才是TimSort
//TImSort中分区run是已有序的子序列
ComparableTimSort ts = new ComparableTimSort(a, work, workbase, workLen); //这里work=null，workbase=workLen=0
//根据待排元素数获取分区run最小长度，使大部分的run的长度达到均衡，有助于后面run的合并操作
//nRemaining<32时，minRun=nRemaining
//nRemaining>=32且nRemaining=2^n时，minRun=16
//nRemaining>=32且nRemaining!=2^n时，16<=minRun<=32
int minRun = minRunLength(nRemaining); //nRemaining=hi-lo，即初始值为待排元素数
do {
//获得下一run长度
//数组a从lo开始的有序子序列长度(严格逆序可通过倒置，也满足有序条件)
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) { //run长度小于最小run长度，需要用二分插入排序补足
int force = nRemaining <= minRun ? nRemaining : minRun;//考虑待排数组最后一个run的特殊情况
binarySort(a, lo, lo + force, lo + runLen);//二分插入排序所少的runLen-force个待排元素
runLen = force; //这里force并不一定等于minRun，最后一个run可能不满足
}
// Push run onto pending-run stack, and maybe merge
//run的起始下标和长度入栈
ts.pushRun(lo, runLen);
//高效率归并部分run
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(); //强制归并所有的run
assert ts.stackSize == 1; //所有run归并后应只剩下一个有序包含所有元素的run
}
//将run的起始下标和长度保存到栈里
private void pushRun(int runbase, int runLen) {
this.runbase[stackSize] = runbase;
this.runLen[stackSize] = runLen;
stackSize++; //stackSize为栈中的run数目
}
//考虑到归并排序的效率问题，因为将一个长序列和一个短序列进行归并排序从效率和代价的角度来看是不划算的，而两个长度均衡的序列进行归并排序时才是比较合理的也比较高效的
private void mergeCollapse() {
//栈中的run数量>1时，才需要合并
while (stackSize > 1) {
int n = stackSize - 2;
//run数量>2且
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n); //归并run[n]和run[n+1]
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}
//根据待排元素数获取分区run最小长度
private static int minRunLength(int n) {
assert n >= 0;
int r = 0; // Becomes 1 if any 1 bits are shifted off
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
来看下mergeAt(int)方法：
@SuppressWarnings("unchecked")
//归并i和i+1 run，其中i=stackSize-2 或 stackSize-3
private void mergeAt(int i) {
assert stackSize >= 2;
assert i >= 0;
assert i == stackSize - 2 || i == stackSize - 3;
int base1 = runbase[i];
int len1 = runLen[i];
int base2 = runbase[i + 1];
int len2 = runLen[i + 1];
assert len1 > 0 && len2 > 0;
assert base1 + len1 == base2; //归并的两个run必须连续的
runLen[i] = len1 + len2;
//若i = stackSize - 3，因为要归并i和i+1，因此先删除i+1(i+2顶替i+1)
if (i == stackSize - 3) {
runbase[i + 1] = runbase[i + 2];
runLen[i + 1] = runLen[i + 2];
}
stackSize--; //二合一后run数-1
//向a[base1]右边飞奔，二分查找a[base2]在run1中的位置
//k是距离a[base1]的位置
int k = gallopRight((Comparable
来看下强制归并所有的方法mergeForceCollapse：
private void mergeForceCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
}
}
至此，无比较器的排序已经分析完，有比较器的排序同无比较器的一样，只是比较方式变了而已。
总结用途来表示Collections.sort排序的大致过程：
接下来看下默认使用的TimSort排序算法：
这里还要注意两点：
- 上图中mergeCollapse()方法尽可能多的归并run，尽量避免一个较长的有序片段和一个较小的有序片段进行归并，因为这样的效率比较低，
即不满足不等式：
runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
runLen[i - 2] > runLen[i - 1]
则归并。 - 在归并两个run过程中同样做了优化，主要是采用了所谓的飞奔(gallop)模式，减少参与归并的数据长度。
假设需要归并的两个已有序片段分别为X和Y，如果X片段的前m个元素都比Y片段的首元素小，那么这m个元素实际上是不需要参与归并的，因为归并后这m个元素仍然位于原来的位置。同理如果Y片段的最后n个元素都比X的最后一个元素大，那么Y的最后n个元素也不必参与归并。这样就减少了归并数组的长度，也减少了待排序数组与辅助数组之间数据来回复制的长度，进而提高了归并的效率。
参考：
Timsort原理介绍
简易版的TimSort排序算法
如何找出Timsort算法和玉兔月球车中的Bug？★
