码农老张 后端
最近
代码解读复制代码 // 数组排序
public static <T> 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);
}
}
// legacyMergeSort的排序实现
private static void mergeSort(Object[] src, // 源数组，从零开始
Object[] dest, // 源数组的克隆体，用于执行排序
int low, // 开始索引
int high, // 结束索引
int off
) {
int length = high - low; // 计算索引范围
// 当length<7进行插入排序，INSERTIONSORT_THRESHOLD=7
// 插入排序，将每个元素放在对应的位置上
if (length < INSERTIONSORT_THRESHOLD) {
// i指待排序元素
for (int i=low; i<high; i++)
// 从i开始由后向前遍历，当dest[j-1]>dest[j]，则进行交换
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
// 数组交换元素
swap(dest, j, j-1);
return;
}
// 递归对数组进行折半
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);
// 如果list已经有序, 只需要拷贝src到dest数组。
// 目前左边数组有序，右边数组有序，则左边最大值小于等于右边最小值，则一定有序
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
// 由源数组src的low开始，拷贝到dest数组，destlow开始，长度为length
System.arraycopy(src, low, dest, destLow, length);
return;
}
// 已排好序的两数组，从小开始比较，小的先出
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
// p从开始到中间（左），q从中间到最后（右），当src[p]<=src[q]，则dest[i]=src[p]，否则dest[i]=src[q]
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。Timsort算法的过程包括
- 如何数组长度小于某个值，直接用二分插入排序算法
- 找到各个run，并入栈
- 按规则合并runjava
代码解读复制代码 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;
int nRemaining = hi - lo;
// 递归结束条件，nRemaining排序数组长度，数组长度为0或者1的时候已经有序。
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// 当数组很小时，使用mini-TimSort，而不归并，长度阀值时32
if (nRemaining < MIN_MERGE) {
// 正数统计升序个数，负数统计降序个数
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// 二分插入排序
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
* 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);
// 拆分大数组成不大于32的n等份，每份数量是minRun，然后逐份插入排序
int minRun = minRunLength(nRemaining);
do {
// 正数统计升序个数，负数统计降序个数
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
// force为minRun与nRemaining的最小值
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();
// 指向下一组数据开头
lo += runLen;
// 待排序数量减少
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
代码解读复制代码 // 优化后的插入排序方法，start代表从start后的元素执行插入，start以前已有序
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
// 最右边初始值
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
// 在已有序的部分，找寻pivot应当插入的地方
// 利用二分法定位应当插入的位置
while (left < right) {
int mid = (left + right) >>> 1;
// 当最右面的初始值比中值小
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
// 数组移位
// switch语句是一条小优化，1-2个元素的移动就不需要System.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] = pivot;
}
}
参考文章：Timsort详解
用于数值（numerical）的排序
代码解读复制代码 // list接口默认排序，原理为转化为数组的排序，排序完成写回数组
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);
}
}
