Comparable和Comparator源码解析

101 阅读 0 评论 67 点赞

我是靠谱客的博主舒心钢笔，这篇文章主要介绍Comparable和Comparator源码解析，现在分享给大家，希望可以做个参考。

我们在排序时，CollectionUtils提供了sort方法，方法如下：

复制代码

1
2
3
4
5
6
7
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}

使用如下：首先创建两个类，ComparbleDemo和ComparatorDemo,如下：

复制代码

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
public class ComparableDemo implements Comparable<ComparableDemo>{
private Integer age;
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public int compareTo(ComparableDemo o) {
return this.age.compareTo(o.getAge());
}
@Override
public String toString() {
return "ComparableDemo{" +
"age=" + age +
'}';
}
}
public class ComparatorDemo {
private Integer age;
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
return "ComparatorDemo{" +
"age=" + age +
'}';
}
}

测试类如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
ArrayList<ComparableDemo> objects = new ArrayList<>();
for (int i = 6; i > 0; i--) {
ComparableDemo comparableDemo = new ComparableDemo();
comparableDemo.setAge(10 + i);
objects.add(comparableDemo);
}
Collections.sort(objects);
System.out.println("objects: " + objects);
ArrayList<ComparatorDemo> objects2 = new ArrayList<>();
for (int i = 6; i > 0; i--) {
ComparatorDemo comparatorDemo = new ComparatorDemo();
comparatorDemo.setAge(10 + i);
objects2.add(comparatorDemo);
}
Collections.sort(objects2, new Comparator<ComparatorDemo>() {
@Override
public int compare(ComparatorDemo o1, ComparatorDemo o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println("objects: " + objects2);
}

从代码中我们可以看出，使用Comparable的时候，List中的类必须实现Comparable接口,而Comparator只需在调用Collections的sort方法时实现即可，所以Comparable在使用时的代码耦合性更高，其实Comparable和Comparator底层的实现方法是一样的，源码如下：
追踪源码我们可以发现Collections的sort方法调用的是Arrays的sort方法，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
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);
}
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

从源码中可以看出Comparable调用的是ComparableTimeSort的sort方法：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
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) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}

然后调用的是ComparableTimeSort的countRunAndMakeAscending方法：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
assert lo < hi;
int runHi = lo + 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;

}
最后调用的是ComparableTimeSort的reverseRange方法

复制代码

1
2
3
4
5
6
7
8
9
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;
}
}

而Comparator调用的是TimSort的sort方法，源码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
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) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}

然后调用的是TimSort的countRunAndMakeAscending方法：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 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;

}

最后调用的是TimSort的reverseRange方法：

复制代码

1
2
3
4
5
6
7
8
9
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;
}
}

从源码中我们可以看到Comparable和Comparator最后的调用的方法是一样的，都是对一个对象的数组进行了一次遍历排序。

jdk8以后，我们可以使用lambda表达式，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test {
public static void main(String[] args) {
ArrayList<ComparatorDemo> objects2 = new ArrayList<>();
for (int i = 6; i > 0; i--) {
ComparatorDemo comparatorDemo = new ComparatorDemo();
comparatorDemo.setAge(10 + i);
objects2.add(comparatorDemo);
}
/* Collections.sort(objects2, new Comparator<ComparatorDemo>() {
@Override
public int compare(ComparatorDemo o1, ComparatorDemo o2) {
return o1.getAge() - o2.getAge();
}
});*/
Collections.sort(objects2, Comparator.comparing(ComparatorDemo::getAge));
System.out.println("objects: " + objects2);
}