发布时间:2024-07-04 14:01
在文章:Java自定义Comparator实现复杂排序 中我们讨论了如何自定义Comparator实现复杂排序,其中聊到Comparator接口的compare(T o1, T o2)
方法中:o1 和 o2的在排序前集合中的顺序为:o2在o1前面。为什么是这样的呢?自定义的Comparator是如何使用到的?
本文我们就撸一撸JDK中List.sort()的源码,找一下哪里使用到了我们自定义的Comparator。
接着博文Java自定义Comparator实现复杂排序中的内容,我们打断点做debug;
我们发现在users.sort()方法出按F7不会进入sort()方法内部,莫方,由于我们实例的List对象是ArrayList,我们进入ArrayList类中找到sort()方法,把断点安排上;
再debug,发现可以进入sort()方法了:
最终进入到TimeSort.sort()方法;其中采用快速排序算法对数组进行排序;我们发现只有两处方法实质用到了传入的Comparator,这两个方法是 负责查出数组一直到第几个数为止有序的countRunAndMakeAscending(a, lo, hi, c)
方法 和 负责对数组进行快速排序的binarySort(a, lo, hi, lo + initRunLen, c)
方法;即Comparator的底层实现原理就体现在这两个方法中,下面我们分开来讨论一下,Comparator在其中充当什么角色?
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
// lo表示数组的起始位置 即:数组下标0
assert lo < hi;
int runHi = lo + 1;
// hi表示数组长度
if (runHi == hi)
return 1;
// c.compare()方法就是我们自定义的
// 如果按照指定规则数组的前一段是“降序”的,需要反转为正序
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
// 从这里可以看到传入到compare(o1, o2)方法的参数,在原数组中 o2 在 o1 前面
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++;
}
// 表示 runHi -lo个元素已经按规则“正序”排好序了
return runHi - lo;
}
countRunAndMakeAscending()方法 返回 按照指定排序规则(这个排序规则就是我们定义的Comparator中的compare()方法,返回-1表示“降序”,即需要反转的意思。)数组中升序的那一段元素的个数 或 反转后 数组中降序的那一段元素的个数。
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;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
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 (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;
}
}
binarySort()方法逻辑:
- 从start(数组中第一个不遵循“升序”规则的数组下标)开始,pivot=array[start],使用二分查找法对start之前已经有序的数组比对,从start下标开始从后往前找,找到start下标之前第一个大于array[start]的元素下标index;
- 将
ndex, start-1
]范围内的数组值都向后移动一位
,放在[index+1~start]
,再把pivot的值赋予array[index](即array[index]=pivot
);- start++,然后执行1,2步骤直到
start==array.klength结束
。
在这里,我们定义的Comparator中的compare()方法充当着排序规则
这个角色,返回-1表示“降序”,即需要反转为“升序”;返回0 和 1表示“升序”,即顺序不变。
我们自定义的Comparator或者默认的Comparator,都是作为一个排序规则最终传递到TimeSort#binarySort()方法中:
- 返回-1表示“降序”,需要交换两个数据的位置,即反转为“升序”;
- 返回0 和 1表示“升序”,即两个数据的位置顺序不变。