章节索引
前提
在处理与线性数据结构有关的问题的时候，经常需要用到排序。我们知道，对于基础类型的数组，我们可以用
Arrays.sort()
这个函数来进行排序，方便又快捷。
但是对于泛型列表类型
List
，我们就束手无策了。
这篇博文主要总结对各类线性数据结构的排序方法。
对基础类型和封装类型的数组进行排序
所谓基础类型，即
int
、
double
、
boolean
、
char
等；所谓封装类型，即
Integer
、
Double
、
String
、
Boolean
等。当我们需要对它们构成的数组进行排序时，可以调用
Arrays.sort()
函数来做，它内部使用归并排序，时间消耗上比快速排序要稳定。
举一个例子：
int[] array = new int[]{1, 9, 3, 7, 4, 6, 8, 2, 5};
Arrays.sort(array);
排序结果：
1 2 3 4 5 6 7 8 9
默认排序规则
针对每种数据类型，
Arrays.sort()
函数都有默认的排序规则，总体上依照数值上小的在前面，大的在后面这样的规则。
int
、
float
、
double
、
Integer
、
String
、
Boolean
这类的就不用多说了，按数值大小排；
char
按照字符
ASCII
码的大小来排；
String
从每个字符串的第一个字符开始比较
ASCII
码，小的在前，大的在后；
Boolean
按照
false < true
的规则进行排序
......
对泛型列表List<T>进行排序
泛型列表
List<T>
是除数组外，我们最经常用到的线性数据结构。与数组相比，它的优点在于
可变长。
比如我们可以定义以下的List：
List<Integer> nums = new ArrayList<>();
class User {
int id;
int age;
String name;
}
List<User> users = new ArrayList<>();
对List进行排序，我们可以调用Collections.sort()函数，他有两个重载：
sort(List<T> list)
sort(List<T> list, Comparator<? super T> c)
对于上述
nums
这种只存单值的列表来说，用第一个重载就可以，默认的排序规则就可以满足要求。
对于上述
users
这种存放自定义类型的列表来说，我们所需的排序规则可能会根据需求发生变化，比如，我需要根据年龄
age
排序，或者我需要根据姓名
name
排序，那么此时就需要上述的第二种重载，由此我们就需要引入比较器
Comparator
。
比较器Comparator
Comparator
是一个类，需要自定义一个Comparator时需要继承它然后实现
compare
方法。
该方法的返回值为
int
型，它关注的是两个被比较的对象何时
算作
前者大于后者（返回1）、何时
算作
相等（返回0）、以及何时
算作
后者大于前者（返回-1）。
举例说明：
private class UserAgeComparator implements Comparator<User> {
@Override
public int compare(User a, User b) {
return a.age < b.age ? -1 : a.age == b.age ? 0 : 1;
}
}
这里用了两个嵌套三元运算符
?:
来比较用户
a
和
b
的年龄
age
，当
a.age > b.age
时返回
1
，当
a.age < b.age
时返回
-1
，否则返回
0
。
执行排序
执行排序的时候，只需要调用
Collections.sort()
函数，传入待排序的列表和自定义的比较器的
实例
：
Collections.sort(users, new UserAgeComparator());
亲测速度很快，再也不用背快排算法了，哈哈。
后记
1. 深究一下Collections.sort()的实现：
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
可以看到，它调用了
List
的
sort
函数，再点进去：
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);
}
}
可以看这个函数的前两行，它实际就是把
list
用
toArray
函数转换成数组，然后调用的是
Arrays.sort()
需要传入比较器的那个重载。
2. 比较器的lambda表达式写法
最近在做题看别人的代码时，发现Comparator可以用lambda表达式简写，
尤其是比较器我们经常也是只用一次，没有必要单写一个内部类出来，代码会简洁很多。
同样针对上述的
User类
，以下是比较器的简写形式：
(a, b) -> (a.age < b.age ? -1 : a.age == b.age ? 0 : 1);
比较器的返回值不一定要是
-1, 0, 1
，只要能区分两个数之间的大小就可以了，所以我们可以简写做：
(a, b) -> (a.age - b.age);
用法如下：
//假设points是一个二维数组，每行的0,1两位存一个点的横纵坐标。对每个点按横坐标排序
Arrays.sort(points, (a, b) -> (a[0] - b[0]));
//假设users是一个List<User>。对每个用户按年龄排序
Collections.sort(users, (a, b) -> (a.age - b.age));