java comparator 降序排序_【转】java comparator 升序、降序、倒序从源码角度理解
原文鏈接：https://blog.csdn.net/u013066244/article/details/78997869
環境
jdk:1.7+
前言
之前我寫過關于comparator的理解，但是都理解錯了。
java 自定義排序【Comparator升序降序的記法】
特別是 上面這篇，完全理解錯了，排序的真正的意思。
最近通過查看源碼，打斷點的方式，一步步的查看、演算。算是明白了！
當時我心里的疑惑是：
① -1到底表示不表示倒序；
② -1、0、1這三個值真的需要同時使用嗎？能不能只使用其中某個就行了。
③-1是不是就是表示不調整順序，其他都是要調整順序。
真正正確的理解：
① jdk官方默認是升序，是基于：
< return -1
= return 0
> return 1
1
2
3
官方的源碼就是基于這個寫的；可以理解為硬性規定。
也就是說，排序是由這三個參數同時決定的。
如果要降序就必須完全相反：
< return 1
= return 0
> return -1
1
2
3
為什么呢？這個只能通過源碼的方式去看了。
測試代碼
首先，我寫了如下的測試代碼:
public static void main(String[] args) {
List re = new ArrayList<>();
re.add(1);
re.add(2);
re.add(6);
re.add(5);
re.add(8);
re.add(8);
re.add(4);
Collections.sort(re, new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
//下面這么寫，結果是降序
if(o1 < o2){
return 1;
}else if(o1 > o2){
return -1;
}
return 0;
}
});
System.out.println(re);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
降序
開始debug測試：
第一步： 程序先調用如下方法：
@SuppressWarnings({"unchecked", "rawtypes"})
public static void sort(List list, Comparator super T> c) {
list.sort(c);
}
1
2
3
4
第二步： 而list.sort(c)源碼：
這里調用的是ArrayList類的方法：
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator super E> c) {
Object[] a = this.toArray();
// 主要看到這里
Arrays.sort(a, (Comparator) c);
ListIterator i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
1
2
3
4
5
6
7
8
9
10
11
第三步：調用Arrays.sort(a, (Comparator) c);方法：
public static void sort(T[] a, Comparator super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
//接下來會走這個方法，上面不會走；
//未來jdk會棄用legacyMergeSort方法。
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
第四步：TimSort.sort(a, 0, a.length, c, null, 0, 0);這個方法很長，我先貼出主要核心的：
if (nRemaining < MIN_MERGE) {
int initRunLen =
//這個方法就大致決定是順序
countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
1
2
3
4
5
6
7
第五步：countRunAndMakeAscending方法：
private static int countRunAndMakeAscending(T[] a, int lo, int hi, Comparator super T> c) {
// lo 是數組起始位置 也就是 0
assert lo < hi;
// runHi = 1，這個值會隨著循環而改變，表示當前元素的位置
int runHi = lo + 1;
// hi是數組長度
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
//這里c.compare()調用就是我們重寫的方法
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
這個方法就是關鍵；
我上面創建了一個數組：
1 2 6 5 8 8 4
//其中
< 1
= 0
> -1
1
2
3
4
5
if (c.compare(a[runHi++], a[lo]) < 0) — 這句代碼，對我的測試代碼而言：if (c.compare(2, 1) < 0)中c.compare(2,1)得到的就是-1。接著就是執行：
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
1
2
3
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)中c.compare(a[runHi], a[runHi - 1]) < 0)就是c.compare(6, 2) < 0)，而c.compare(6, 2)返回的是-1，所以會接著循環執行，runHi++后,此時runHi=2。就我的測試代碼就會去判斷c.compare(5, 6)，其返回的是1，循環結束，接著執行reverseRange(a, lo, runHi);。這個是個反轉方法。
效果就是：
數組：1 2 6 5 8 8 4
反轉后：6 2 1 5 8 8 4
1
2
可以看出，前面三個數字順序已經好了，后面的5 8 8 4，會在執行binarySort(a, lo, hi, lo + initRunLen, c);這個方法時來進行二分插入排序。
第六步：執行binarySort(a, lo, hi, lo + initRunLen, c);方法：
private static 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) {
//這里相當于除以2
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
//當left等于right時，就說明找到位置了。
//assert是斷言，要是為false會直接報錯
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;
//要是移動的位數大于2，就執行如下方法；
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
例子中的數組：
6 2 1 5 8 8 4
//循環執行binarySort方法后，
//會依次把 5 8 8 4 插入到相應的位置
//最終的結果為：
// 8 8 6 5 4 2 1
1
2
3
4
5
升序
這是，jdk默認的順序，例子：
< -1 > 1 =0
1 2 6 5 8 8 4
1
2
執行步驟和上面降序是一樣的，我就直接分析核心部分了：
// 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++;
}
1
2
3
4
5
6
7
8
9
當執行到這里時，c.compare(a[runHi++], a[lo]) < 0就是c.compare(2, 1) < 0，而`c.compare(2, 1)返回的是1，那么程序就會進入else的部分：
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
1
2
代碼c.compare(a[runHi], a[runHi - 1])就是c.compare(6, 2)返回的是1符合條件(大于0)，
runHi++,此時runHi=3。c.compare(a[runHi], a[runHi - 1])就是c.compare(5, 6)，其返回的是-1，不符合條件。循環結束，數組結果為：
//可以看出什么都沒有變
1 2 6 5 8 8 4
//但是方法的`return runHi - lo;`這個返回的結果就是3
//這個返回值，會在`binarySort(a, lo, hi, lo + initRunLen, c);`中用到。
1
2
3
4
下一步：執行binarySort(a, lo, hi, lo + initRunLen, c);其中initRunLen = 3；
在執行二分插入時，就會從數組下標為3開始；
1 2 6 5 8 8 4
//從下標為3，開始二分插入排序；即從5開始。
1 2 5 6 8 8 4
接著是8
1 2 5 6 8 8 4
接著是第二個8
1 2 5 6 8 8 4
接著是4
1 2 4 5 6 8 8
1
2
3
4
5
6
7
8
9
通過升序和降序，我們基本可以知道排序步驟：
①countRunAndMakeAscending這個方法確定是順序還是降序，并且將數組的一部分排列好。并返回未排列的起始位置
②將未排列的起始位置傳遞給binarySort進行二分插入排序。
倒序
我們先來看看倒序的結果：
1 2 6 5 8 8 4
倒序后：
4 8 8 5 6 2 1
//怎么做到呢？
//不管大于、小于和等于 都返回 -1
1
2
3
4
5
從源碼上看countRunAndMakeAscending方法：
f (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++;
}
1
2
3
4
5
6
7
8
c.compare()得到的永遠都是-1，所以其會將下面這段代碼執行完畢：
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
1
2
循環完畢后，此時runHi就是數組的長度7。
接著執行reverseRange(a, lo, runHi);，將整個數組進行倒序。
該方法完全執行完成后，返回值就是數組長度。
此時再執行binarySort方法時，for ( ; start < hi; start++)中的start是剛剛傳進來的值，也就是數組長度，而hi也是數組長度，所以二分插入方法什么都沒有做，只是調用了下。
0 到底是什么作用
假設不管大于、小于、等于，我們都返回0 ，會發現順序沒有變；而且你會發現，要是都返回1的話，順序也是沒有變的！
從countRunAndMakeAscending方法中可以得出結論：
// 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 {
//走這個循環
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
1
2
3
4
5
6
7
8
9
10
當不管大于、小于、等于時，我們都返回一個值時，0和1效果是一樣的，就是不排序；-1就是倒序。
可以要是 是如下寫法：
public int compare(Integer o1, Integer o2) {
if(o1 < o2){
return 1;
}/*else if(o1 > o2){
return 1;
}*/
return -1;
}
1
2
3
4
5
6
7
8
也就是 我們把等于和大于都返回-1，小于返回1。發現也是可以降序的，或者反過來，就是升序。視乎覺得0好像是多余的。
其實0表示的是，相同元素不排序，要是我們把等于返回為-1，那么兩個相同的元素會交互順序；
1 2 6 5 8 8 4
//也就是這里面兩個8 會交換順序
1
2
對數字而言交換順序沒有關系，但是里面要是是Map對象的話，那就有關系，因為有時我們是希望相同元素不進行順序調整的。
要是我們把等于返回為1效果和0是一樣的都是不排序。
總結
排序其實是由三個數字同時決定的；
升序(默認，即官方定義，畢竟代碼實現就是基于這個寫的)：
< -1
= 0 //或者 1效果是一樣的；-1相同元素會發生位置調整
> 1
1
2
3
降序：
< 1
= 0 //或者 1效果是一樣的；-1相同元素會發生順序調整
> -1
1
2
3
倒序：
//直接
return -1;
1
2
不改變順序：
//直接
return 0或者1;
1
2
底層做法是：先確定局部順序，再利用二分查找法，進行后續排序：
數組：1 2 6 5 8 8 4
反轉后：6 2 1 5 8 8 4
1
2
這里先確定了6 2 1的順序，后面5 8 8 4的位置就是利用二分查找法來確定的！
---------------------
作者：山鬼謠me
來源：CSDN
原文：https://blog.csdn.net/u013066244/article/details/78997869
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的java comparator 降序排序_【转】java comparator 升序、降序、倒序从源码角度理解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java程序发送邮件_用java程序发送
- 下一篇： java struts json_str