前几天在 LeetCode 刷题的时候，遇到了利用 Arrays.sort() 或 Collections.sort() 来对 Java 对象进行排序的需求，于是想较详细地总结一下 Java 对象的排序实现方法，这些方法能让我们的编程更快捷。
在 Java 中，基本使用两种方法，即 Comparator 和 Comparable 接口，来完成基本甚至稍微复杂一点的排序的任务。当然，面对不同的数据结构，如数组（Array）、集合（Set）或映射（Map），排序的实现方式稍有不同。
要排序的对象
本文的任务就是对一系列的 Person 类对象进行排序，其中 Person 类的定义如下，
/** 原始 Person 类，每个对象包含 name 人名和 age 年龄属性 */
class Person {
String name; // 人名
int age; // 年龄
public Person(String n, int a) {
this.name = n;
this.age = a;
}
/** 重写 Object 的 toString() 方法，便于打印对象 */
@Override
public String toString() {
return ("name:" + this.name + ", age:" + this.age).toString();
}
}
方法1： 使用 Comparable 接口
Comparble 接口的使用方法很直观，在要比较的对象的类的声明中实现 Comparable 接口即可。例如我们想要对 Person 对象进行排序，首先在 Person 类的声明中加上 implements Comparable<Person> 的语句，然后重写 Comparable 接口的 compareTo 的方法，按照比较规则返回 1，-1 或者 0。示例代码如下，
/** 实现了 Comparable 接口的 Person 类，
* 每个 Person 对象都是可比较的，比较的依据是 age 属性。
* */
class Person implements Comparable<Person>{
String name; // 人名
int age; // 年龄
public Person(String n, int a){
this.name = n;
this.age = a;
}
/** 重写 Comparable 的 compareTo 方法，表示按照人的年龄来排序 */
@Override
public int compareTo(Person p2){
if(this.age > p2.age){
return 1;
}else if(this.age < p2.age){
return -1;
}else{
return 0;
}
}
/** 重写 Object 的 toString() 方法，便于打印对象 */
@Override
public String toString(){
return ("name:" + this.name + ", age:" + this.age).toString();
}
}
在声明了上述的 Person 对象后，从根本上让 Person 对象具有了“可比较”的特性，我们直接利用 Arrays.sort() 或者 Collections.sort() 来比较一系列的 Person 对象了。示例代码如下，
import java.util.Arrays;
public class HelloWorld{
public static void main(String []args){
// 构建 Person 对象数组，包含 5 个对象
Person[] ps = new Person[5];
ps[0] = new Person("John", 30);
ps[1] = new Person("Mike", 22);
ps[2] = new Person("Kim", 34);
ps[3] = new Person("Canddy", 25);
ps[4] = new Person("Sam", 28);
// 利用 sort 方法对 Person 数组进行排序
Arrays.sort(ps);
// 打印 Person 数组
for(int i=0; i<ps.length; i++){
System.out.println(ps[i]);
}
}
}
执行上述代码可以得到新的数组，我们打印这个数组，其输出确实是按照人的年龄排序的。而且 sort() 函数的排序效率较高，因此可以把排序数组放心的交给它。
这里插一句题外话，根据 Java 8 源码可知，Arrays.sort() 函数内部使用的排序算法是一种包含多种基本排序算法的混合算法1。
在 Java 实现中，Arrays.sort()（主要针对数组）或 Collections.sort()（主要针对列表）底层使用了多种算法，大概的思路为，
1 - 当元素个数小于 47 时，使用 插入排序算法（时间复杂度 O(n^2)）；
2 - 当元素个数大于等于 47 且小于 286 时，使用 快速排序算法（时间复杂度 O(n × \times ×log(n))）；
3 - 当数组个数大于等于 286 时，使用 归并排序算法（时间复杂度O(n × \times ×log(n))，空间复杂度 O(n)）。
方法 2：使用 Comparator 接口
上一节的比较对象的方式需要我们让对象类实现 Comparable 接口并重写 compareTo 方法，但当我们没有办法改变对象类的实现，只能靠外部来对对象进行排序时，就只能使用 Comparator 接口了。
在编程中，Comparator 接口一般被匿名继承并作为第二个参数传递给 Arrays.sort() 函数。按照上一节的例子，假设我们不能对 Person 类进行修改（使用原始的 Person 类），我们可以使用如下代码对其对象数组进行排序。
import java.util.Arrays;
import java.util.Comparator;
public class HelloWorld{
public static void main(String []args){
// 构建 Person 对象数组，包含 5 个对象
Person[] ps = new Person[5];
ps[0] = new Person("John", 30);
ps[1] = new Person("Mike", 22);
ps[2] = new Person("Kim", 34);
ps[3] = new Person("Canddy", 25);
ps[4] = new Person("Sam", 28);
// 利用 sort 方法对 Person 数组进行排序
Arrays.sort(ps, new Comparator<Person>(){
/** 重写 compare 方法来对 Person 对象进行比较 */
@Override
public int compare(Person p1, Person p2){
if(p1.age > p2.age){
return 1;
}else if(p1.age < p2.age){
return -1;
}else{
return 0;
}
}
});
// 打印 Person 数组
for(int i=0; i<ps.length; i++){
System.out.println(ps[i]);
}
}
}
可见比较的结果与使用 Comparable 接口的方法相同。
由于 Comparator 是函数式接口（只有一个抽象函数的接口），我们也可以使用 Lambda 表达式来让代码更简洁，此时只需要把核心代码改为，
// 利用 lambda 表达式来简化代码
Arrays.sort(ps, (Person p1, Person p2) -> {
if(p1.age > p2.age) return 1;
else if(p1.age < p2.age) return -1;
else return 0;
});
这里插一句题外话，如果比较的是字符串，Java 提供了一个很好的比较方法，即 compareTo(String s)，该方法能自动返回 2 个字符串大小比较的结果，比如说我们此处按照人名来排列，那么代码应该为，
Arrays.sort(ps, (Person p1, Person p2) -> {
return p1.name.compareTo(p2.name);
});
Java 在实现 String 类（字符串类）的时候，为了方便字符串比较，也让 String 类实现了 comparable 接口，因此每个 String 对象均有 compareTo() 方法。该方法会从 2 个字符串首个字母开始，依次比较对应位置上的字符的 ASCII 码值，值越大的字符串更大2 。如 “aba”,“abb”,“abab” 的排序结果是 “aba”, “abab”, “abb”。
集合（Set）对象的排序
当 Person 对象出现在集合中时，如 HashSet 中时，我们是无法对集合中的元素进行排序的，这时候我们应该思考使用可替代的数据结构。这里给出使用 TreeSet 来对元素进行排序的实例，
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
public class HelloWorld{
public static void main(String []args){
// 构建 Person 对象集合，包含 5 个对象
Set<Person> psSet = new TreeSet<Person>(new PersonComparator());
psSet.add(new Person("John", 30));
psSet.add(new Person("Mike", 22));
psSet.add(new Person("Kim", 34));
psSet.add(new Person("Canddy", 25));
psSet.add(new Person("Sam", 28));
// 打印 Person 数组
for(int i=0; i<psList.size(); i++){
System.out.println(psList.get(i));
}
}
}
/** Person 类的比较器 */
class PersonComparator implements Comparator<Person>{
@Override
public int compare(Person p1, Person p2) {
if(p1.age > p2.age){
return 1;
}else if(p1.age < p2.age){
return -1;
}else {
return 0;
}
}
}
TreeSet 的元素对象类继承 Compable 接口或提供一个继承 Comparator 的比较器。类似的，你也可以让 Person 类实现 Comparable 接口来让 TreeSet 中的元素变得有序。
映射（Map）对象的排序
Java 中的映射是一个 key-value 的键值对，我们既可以按照 key 排序，也可以按照 value 来排序。如果我们使用的是 TreeMap，那么该映射会自动按照 key 值进行排序；如果我们使用的是 HashMap，那么该映射的输出顺序是不定的。
但是无论针对哪一种映射结构，我们对其中的元素进行排序的方法都是固定的，也就是首先将映射中的所有 Entry 单元存放到一个 ArrayList 列表中去，然后对这个 ArrayList 进行排序。具体的实例代码如下，
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class HelloWorld{
public static void main(String[] argv) {
// 映射中初始有 5 个元素，key 为姓名，value 为年龄
Map<String, Integer> psMap = new HashMap<String, Integer>();
psMap.put("John", 30);
psMap.put("Mike", 22);
psMap.put("Kim", 34);
psMap.put("Canddy", 25);
psMap.put("Sam", 28);
// 将映射中的 Entry 对象放入 ArrayList 中并排序
List<Map.Entry<String, Integer>> list = new ArrayList<>(psMap.entrySet());
Collections.sort(list,
(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) -> {
if(e1.getValue() > e2.getValue()) return 1;
else if(e1.getValue() < e2.getValue()) return -1;
else return 0;
});
// 打印映射中的元素
for(int i=0; i<list.size(); i++) {
System.out.println(list.get(i).getKey() + ": " + list.get(i).getValue());
}
}
}
在 java 中，映射的底层实现是数组加链表（或红黑树）3，想要原地对映射进行排序是很困难的。因此，将映射中的 Entry 对象放入列表中排序只是一个权宜之计。另外，也建议大家使用 Entryset() 来遍历映射，因为它比使用键值来遍历（即 Keyset()）更加高效。
小总
Java 对象的排序思路主要有 Comparable 和 Comparator 接口两种办法。前者让对象本身具有“可比较”的属性，即让对象类继承 Comparable 接口，重写 compareTo 方法；后者创建一个继承 Comparator 接口的比较器 XXCompartor，重写 compare 方法，最后将该比较器作为参数传递给 Arrays.sort() 或 Collection.sort() 方法。
针对不同数据结构中的对象，我们可以灵活设计排序方法。对于数组，我们使用 ArrayList.sort()；对于列表，我们使用 Collections.sort()；对于集合，我们使用 TreeSet 的数据结构；对于映射，我们针对每个 Entry 对象进行排序。
参考：