Java 6 中 sort 方法默认采用的是传统快速排序。
Java 7 开始则使用改进版的双轴快速排序(DualPivotQuicksort)。
Java 8 中 Arrays 的排序方法只提供了两种算法的实现
- sort 方法：基础类型双轴快速排序(DualPivotQuicksort)算法，对象排序使用 TimSort 算法。
- parallelSort 方法：并行排序算法。
Collections 提供了两种排序方式
Collections.sort(List<T> list)Collections.sort(List<T> list, Comparator<? super T> c)
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
|
public class Collections {
private Collections() {
}
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);
}
}
public interface List<E> extends Collection<E> {
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);
}
}
}
public class Arrays {
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);
}
}
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
}
|
常用接口:
1
2
3
4
5
6
7
8
9
|
// 数组排序
// 字符数组，元素的自然顺序进行升序排序，大小写不敏感
Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
// 降序排序
Arrays.sort(intArray,Comparator.reverseOrder());
// 集合排序
Collections.sort(list,Collectons.reverseOrder());
Collections.reverse(Arrays.asList(intArray));
|
TimSort 算法
是一种起源于归并排序和插入排序的混合排序算法，设计初衷是为了在真实世界中的各种数据中可以有较好的性能。
- 利用待排序数据可能部分有序的事实，
- 依据待排序数据内容，动态改变排序策略——选择性进行归并以及galloping
基本工作过程是：
- 扫描数组，确定其中的单调上升段和严格单调下降段，将严格下降段反转；
- 定义最小基本片段长度，短于此的单调片段通过插入排序集中为长于此的段；
- 反复归并一些相邻片段，过程中避免归并长度相差很大的片段，直至整个排序完成，所用分段选择策略可以保证O(n
log n)时间复杂性。
可以看到，原则上TimSort是归并排序，但小片段的合并中用了插入排序。
Comparable<T>
实现了 Comparable 接口，就意味着``该类支持排序’’。
可以通过 Collections.sort(List<T> list)
方式称为自然排序（一般是升序），参与排序的对象需实现 Comparable<T>
接口，重写其 compareTo()方法。
此外可以用作有序映射(如TreeMap)''中的键或有序集合(TreeSet)‘‘中的元素，而不需要指定比较器。
1
2
3
4
5
6
7
8
9
10
|
package java.lang;
import java.util.*;
/**
* @see java.util.Comparator
* @since 1.2
*/
public interface Comparable<T> {
public int compareTo(T o);
}
|
- e1.compareTo(e2) > 0 即 e1 > e2
- e1.compareTo(e2) = 0 即 e1 = e2
- e1.compareTo(e2) < 0 即 e1 < e2
Comparator<T>
通过 ``实现 Comparator<T>
类来新建一个比较器’’，然后通过该比较器对类进行排序。
Collections.sort(List<T> list, Comparator<? super T> c) 方式称为自定义排序，实现Comparator<T> 接口，重写其 compare() 方法。
排序逻辑简单可以编写匿名内部类。
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
|
@FunctionalInterface
public interface Comparator<T> {
int compare(T o1, T o2);
}
public class Book implements Comparable<Book> {
private String name;
private int count;
@Override
@Override
public int compareTo(Book book) {
int result;
result = this.count - book.getCount();
if (result == 0){
result = this.name.compareTo(book.getName());
}
return result;
}
}
public void sort(List<Book> list) {
Collections.sort(list);
Collections.sort(list, new Comparator<Book>(){
@Override
public int compare(Book o1, Book o2) {
return o1.getCount() - o2.getCount();
}
});
// JDK 1.8
Collections.sort(userList, Comparator.comparingInt(User::getAge));
}
|
1
2
3
4
5
6
|
studentList.stream()
.sorted(Comparator.comparing(
Student::getMath, Comparator.reverseOrder())
.thenComparing(Student::getEnglish, Comparator.reverseOrder())
.thenComparing(Student::getChinese))
.forEach(System.out::println);
|