我在使用List.sort()方法的自定义比较器排序的时候,想当然认为(O1,O2)->{} o1是集合中前一个元素,o2是后一个元素,返回-1是交换元素位置,1是不交换元素位置,结果我的排序正好和我想要的相反,百度了一下,发现不少讲解帖子也都是错误的,正确的结论是:
o2在o1前面,返回-1 表⽰交换o2 和 o1的顺序;
返回0 和 1都表示不交换o2 和 o1的顺序;
来看一下list.sort()的源码
java/util/ArrayList.java:1460
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
//预期计数,保证对数组每个元素进行排序
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
//预期计数与数组大小不符的话,就抛出一个并发修改异常
throw new ConcurrentModificationException();
}
modCount++;
}
再点进去
java/util/Arrays.java:1503
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
//没有传比较器的情况,使用默认sort排序
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
再点进去rangeCheck这个方法
java/util/Arrays.java:111
arrayLength--数组长度 fromIndex--开始排序时的索引位置 toIndex--结束排序时的索引位置
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
//开始排序时的索引位置 大于结束排序时的索引位置 抛出参数校验非法异常
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
//数组下标越界异常
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > arrayLength) {
//数组下标越界异常
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
再来这个LegacyMergeSort.userRequested 用户可以设置这个为true来启用传统归并排序,我们不用关心这个
然后看 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
点进去
java/util/TimSort.java:210
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
//断言 当这个返回false是会从这里停止执行代码
//
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
//数组大小为0或者1不需要排序
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
//32 代表数组长度小于此值的时候使用 mini-TimSort 排序
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);
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;
}
首先看第一个 countRunAndMakeAscending
java/util/TimSort.java:347
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
主要看这里这里就是使用我们传入的比较器的地方了
c.compare(a[runHi++], a[lo]) ,a[runHi++]这个就是o1, a[lo] 就是o2
然后看这句int runHi = lo + 1; 既可以得出o1是在o2后的
再看这个 c.compare(a[runHi++], a[lo]) < 0 这是我们返回-1的时候了
runHi < hi && c.compare(a[runHi], a[runHi - 1] <0 这是找出到最后比较索引compare结果小于0的连续区间
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;
}
}
反转上述找出的区间的元素
runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0 就是不反转了
看完源码,和我们的结论一致
这是倒序
(o1,o2)->
{
if (o1 > o2) {
return -1;
} else {
return 1;
}
}
这是正序
(o1,o2)->
{
if (o1 > o2) {
return 1;
} else {
return -1;
}
}