前几天在 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() 函数内部使用的排序算法是一种包含多种基本排序算法的混合算法¹。

在 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 码值，值越大的字符串更大² 。如 “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 中，映射的底层实现是数组加链表（或红黑树）³，想要原地对映射进行排序是很困难的。因此，将映射中的 Entry 对象放入列表中排序只是一个权宜之计。另外，也建议大家使用 Entryset() 来遍历映射，因为它比使用键值来遍历（即 Keyset()）更加高效。

小总

Java 对象的排序思路主要有 Comparable 和 Comparator 接口两种办法。前者让对象本身具有“可比较”的属性，即让对象类继承 Comparable 接口，重写 compareTo 方法；后者创建一个继承 Comparator 接口的比较器 XXCompartor，重写 compare 方法，最后将该比较器作为参数传递给 Arrays.sort() 或 Collection.sort() 方法。

针对不同数据结构中的对象，我们可以灵活设计排序方法。对于数组，我们使用 ArrayList.sort()；对于列表，我们使用 Collections.sort()；对于集合，我们使用 TreeSet 的数据结构；对于映射，我们针对每个 Entry 对象进行排序。

参考：

在这之前，首先来说一下用Android Studio来调试Java程序，控制台出现乱码的问题。至于怎么用Android Studio创建Java程序，网上很多。

public class JavaBase {
    public static void main(String[] args) {
        System.out.println("排序前" );
        }
    }

试了各种方法，都不行，网上的各种方法都是针对Android Project的，最后尝试了下面的方法：

红色箭头的位置，改为GBK就OK了。

下面是对自定义User对象排序的代码：

package com.jackie.java.base;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class JavaBase {
    public static void main(String[] args) {
        User user1 = new User("Jackie", 25);
        User user2 = new User("Jim", 18);
        User user3 = new User("Lucy", 30);
        User user4 = new User("Kate", 18);

//        System.out.print(user1.compareTo(user2));

        List<User> users = new ArrayList<>();
        users.add(user1);
        users.add(user2);
        users.add(user3);
        users.add(user4);

        System.out.println("排序前" );
        for (User user : users) {
            System.out.println(user.getName() + " " + user);
        }

        Collections.sort(users);
        System.out.println("排序后" );
        for (User user : users) {
            System.out.println(user.getName() + " " + user);
        }
    }
}

出现了下面的异常:

很明显，Java中不允许直接对自定义的对象调用sort直接排序，需要实现Comparable接口。按照上面的方法改造一下User.java

方法一：让User对象实现Comparable接口

package com.jackie.java.base;

/**
 * Created by Jackie on 2015/12/21.
 */
public class User implements Comparable<User> {
    private String name;
    private int age;

    public User() {
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }


    @Override
    public int compareTo(User user) {
       return age - user.getAge();
    }
}

调用方法：

Collections.sort(users);

方法二：User对象不作任何改动，添加一个比较器UserComparator.java

package com.jackie.java.base;

import java.util.Comparator;

/**
 * Created by Jackie on 2015/12/21.
 */
public class UserComparator implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        User user1 = (User) o1;
        User user2 = (User) o2;

        if (user1.getAge() > user2.getAge()) {
            return 1;
        } else if (user1.getAge() < user2.getAge()) {
            return -1;
        } else {
            //利用String自身的排序方法。
            //如果年龄相同就按名字进行排序
            return user1.getName().compareTo(user2.getName());
        }
    }
}

调用方法：

Collections.sort(users, new UserComparator());

结果如下：

顺便说一下Comparable和Comparator的区别：

1. Comparable和Comparator都是用来实现集合中元素的比较、排序的，只是Comparable是在集合内部定义的方法实现的排序，Comparator是在集合外部实现的排序，所以想要实现排序，就需要在集合外定义Comparator接口或在集合内实现Comparable接口两种方法。

2. Comparable实现的排序只能是自然排序，这里的自然顺序就是实现Comparable接口设定的排序方式（Demo是按照年龄从小到大排序）。而Comparator是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。比如说，如果把上面的UserComparator.java的方法改为：

public class UserComparator implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        User user1 = (User) o1;
        User user2 = (User) o2;

        if (user1.getAge() > user2.getAge()) {
            return -1;
        } else if (user1.getAge() < user2.getAge()) {
            return 1;
        } else {
            //利用String自身的排序方法。
            //如果年龄相同就按名字进行排序
            return user1.getName().compareTo(user2.getName());
        }
    }
}

可以说一个是自已完成比较，一个是外部程序（自定义比较规则）实现比较的差别而已。

当我们给一个整型数组或者浮点型之类的数组排序的时候，很简单就可以达到我们排序的目的，无非是排序算法的问题。那么，如果我们现在想根据对象的一个属性值给一个对象数组进行排序呢？

假如我们现在有一个Car类型，Car类中有一个double型的speed属性用来描述车辆的速度，现在我们想根据车速来对一个Car数组中的车辆进行排序，怎么做呢？

public class Car{
	private double speed;//车辆的速度属性

	public Car(double speed) {
		this.speed = speed;
	}

	public double getSpeed() {
		return speed;
	}

	public void setSpeed(double speed) {
		this.speed = speed;
	}	
}

麻烦的方法

我们可以通过比较对象的属性值，根据比较结果，对对象数组进行排序，例如，假如我们使用的是冒泡排序的话，就需要写成下面这样：

for(int i=0;i<a.length-1;i++)//a为一个存储了很多Car对象的数组
{
	for(int j=0;j<a.length-i-1;j++)
	{
		if(a[j].getSpeed()>a[j+1].getSpeed())//交换操作
		{
			Car temp=a[j];
			a[j]=a[j+1];
			a[j+1]=temp;
		}
	}
}

这样写确实能实现了效果，但是未必性能很好，由于是自己写的，写起来也会比较麻烦，下面的方法会更好

Arrays.sort()方法

我们先来看看用Array.sort()方法实现对车辆排序的代码：
其中，Car这个类有两种写法：

第一种写法：

public class Car implements Comparable<Car>{
	private double speed;

	public Car(double speed) {
		this.speed = speed;
	}

	public double getSpeed() {
		return speed;
	}

	public void setSpeed(double speed) {
		this.speed = speed;
	}

	@Override
	public int compareTo(Car newCar) {
		return Double.compare(this.getSpeed(),newCar.getSpeed());
	}	
}

第二种写法

public class Car implements Comparable{
	private double speed;

	public Car(double speed) {
		this.speed = speed;
	}

	public double getSpeed() {
		return speed;
	}

	public void setSpeed(double speed) {
		this.speed = speed;
	}

	@Override
	public int compareTo(Object newCar) {
		return Double.compare(this.getSpeed(),((Car)newCar).getSpeed());
	}	
}

main方法：

public class Test8 {
	public static void main(String[] args) {
		Car[] carList = new Car[3];
		carList[0] = new Car(30);
		carList[1] = new Car(10);
		carList[2] = new Car(55);
		Arrays.sort(carList);
		
		for(Car c:carList)
		{
			System.out.println(c.getSpeed());
		}
	}
	
}

输出结果：

解析：

顾名思义，Arrays类的sort()方法是对一个数组进行排序的方法，sort()方法的参数是一个对象数组，也就是要排序的那个数组，但是有些特别的是，这个对象数组中存储的对象的类必须实现了Comparable接口。

Comparable接口是用来比较大小的，要实现这个接口，我们必须重写接口中的CompareTo()方法，这个方法用来比较两个对象的大小，因为方法本身并不知道我我们会根据对象的哪个属性来比较两个对象的大小，因此在这个方法中，我们可以定义我们自己的比较规则。

在上述的代码中，我们调用了Double类的比较方法来比较两个对象的speed属性的大小，如果调用方法的Car对象的speed属性值比方法参数传进来的Car对象的speed值大就返回1，相等就返回0，小于就返回-1。当然，我们也可以自己手写这个部分，无非就是if else判断的事。

之所以有两种写法，是因为第一种使用了泛型，第二种使用了对象的强制转换，可以看到，当我们使用泛型的时候，在调用对象的时候就已经确定了使用接口的时候用的是哪一种对象，因此就不用把对象类型强制转换为我们想要的类型了。而第二种我们没有使用泛型，因此就需要把参数传进来的对象强制转换成我们想要的类型然后再进行操作。推荐使用第一种写法。

接下来，我们在main方法中构建了一个Car类型的数组，然后直接调用Arrays.sort()方法传进数组作为参数就可以对数组进行排序了。

这种方法比较方便，快捷，在性能方面也有不错的表现，本人亲测在排序20万个对象的时候花费差不多200ms左右的时间。

当然，这种方法主要图的是方便，当我们需要排序大量的数据的时候，还是应该结合自己数据的特性来具体选择一种排序方式自己写。