教程：集合
课程：接口

对象排序

一个 List 可以按照以下方式进行排序。

Collections.sort(l);

如果 List 包含 String 元素，它将按照字母顺序进行排序。如果它包含 Date 元素，它将按照时间顺序进行排序。这是如何实现的呢？String 和 Date 都实现了 Comparable 接口。 Comparable 的实现为类提供了一种自然排序，使得该类的对象可以自动排序。下表总结了一些重要的实现了 Comparable 接口的 Java 平台类。

**实现 Comparable 的类**
类	自然排序
`Byte`	有符号数值
`Character`	无符号数值
`Long`	有符号数值
`Integer`	有符号数值
`Short`	有符号数值
`Double`	有符号数值
`Float`	有符号数值
`BigInteger`	有符号数值
`BigDecimal`	有符号数值
`Boolean`	`Boolean.FALSE < Boolean.TRUE`
`File`	与系统相关的路径名字典顺序
`String`	字典顺序
`Date`	时间顺序
`CollationKey`	与特定区域设置相关的字典顺序

如果您尝试对一个不实现 Comparable 的列表进行排序，Collections.sort(list) 将抛出 ClassCastException。类似地，如果您尝试使用 comparator 对一个无法相互比较的元素列表进行排序，Collections.sort(list, comparator) 将抛出 ClassCastException。可以相互比较的元素称为可互相比较的。尽管不同类型的元素可能是可互相比较的，但是这里列出的类不允许进行跨类比较。

如果您只想对可比较元素的列表进行排序或创建排序的集合，那么这就是关于Comparable接口的您真正需要了解的全部内容。如果您想要实现自己的Comparable类型，则下一节将对您有兴趣。

编写自己的可比较类型

Comparable接口由以下方法组成。

public interface Comparable<T> {
    public int compareTo(T o);
}

compareTo方法将接收对象与指定对象进行比较，并根据接收对象是否小于、等于或大于指定对象返回负整数、0或正整数。如果无法将指定对象与接收对象进行比较，该方法将抛出ClassCastException异常。

以下表示人名的类实现了Comparable。

import java.util.*;

public class Name implements Comparable<Name> {
    private final String firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String firstName() { return firstName; }
    public String lastName()  { return lastName;  }

    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name) o;
        return n.firstName.equals(firstName) && n.lastName.equals(lastName);
    }

    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }

    public String toString() {
	return firstName + " " + lastName;
    }

    public int compareTo(Name n) {
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
    }
}

为了使前面的示例简短，该类有一定的限制：它不支持中间名，它要求既有名字又有姓氏，并且在任何方式上都没有国际化。尽管如此，它还是说明了以下重要点：

Name对象是不可变的。其他所有条件相同，不可变类型是最佳选择，特别是用作Set中的元素或Map中的键的对象。如果在集合中修改它们的元素或键，这些集合将会损坏。
构造函数检查其参数是否为null。这确保了所有的Name对象都是良好形式的，因此任何其他方法都不会抛出NullPointerException。
重新定义了hashCode方法。这对于重新定义equals方法的任何类都是必不可少的。（相等的对象必须具有相等的哈希码。）
equals方法如果指定的对象为null或类型不合适，则返回false。如果在这些情况下compareTo方法抛出运行时异常。这两种行为都是各自方法的一般契约所要求的。
重新定义了toString方法，以便以可读形式打印Name。这总是一个好主意，特别是对于要放入集合中的对象。各种集合类型的toString方法依赖于其元素、键和值的toString方法。

由于这一部分是关于元素排序的，让我们再谈谈Name的compareTo方法。它实现了标准的按姓名排序算法，其中姓氏优先于名字。这正是自然排序所需的。如果自然排序不自然，那将非常混乱!

看看compareTo是如何实现的，因为这是相当典型的。首先，你比较对象的最重要的部分（在这种情况下是姓氏）。通常，你可以使用该部分类型的自然排序。在这种情况下，该部分是一个String，自然（字典）排序正是所需的。如果比较结果不为零，表示不相等，那就结束了：你只需返回结果。如果最重要的部分相等，那么就继续比较下一个最重要的部分。在这种情况下，只有两个部分——名字和姓氏。如果有更多的部分，你会按照明显的方式继续比较部分，直到找到两个不相等的部分或者比较到最不重要的部分，此时返回比较的结果。

只是为了展示它的运行方式，这里有一个构建名字列表并对其进行排序的程序。

import java.util.*;

public class NameSort {
    public static void main(String[] args) {
        Name nameArray[] = {
            new Name("John", "Smith"),
            new Name("Karl", "Ng"),
            new Name("Jeff", "Smith"),
            new Name("Tom", "Rich")
        };

        List<Name> names = Arrays.asList(nameArray);
        Collections.sort(names);
        System.out.println(names);
    }
}

如果你运行这个程序，它会打印出以下内容。

[Karl Ng, Tom Rich, Jeff Smith, John Smith]

对于compareTo方法的行为有四个限制，我们暂时不会详细介绍，因为它们相当技术性和乏味，并且最好在API文档中查阅。所有实现Comparable的类都必须遵守这些限制，所以如果你要编写一个实现Comparable的类，请阅读Comparable的文档。试图对违反这些限制的对象列表进行排序会导致未定义的行为。严格来说，这些限制确保自然排序是实现它的类对象的全序，这是确保排序定义良好的必要条件。

比较器

如果你想按照除了自然排序之外的其他顺序对一些对象进行排序怎么办？或者如果你想对一些不实现Comparable接口的对象进行排序怎么办？为了做到这些，你需要提供一个Comparator —— 一个封装了排序顺序的对象。与Comparable接口一样，Comparator接口由一个方法组成。

public interface Comparator<T> {
    int compare(T o1, T o2);
}

compare 方法比较其两个参数，根据第一个参数是否小于、等于、大于第二个参数，返回一个负整数、0 或正整数。如果任一参数的类型对于 Comparator 来说不合适，则 compare 方法抛出一个 ClassCastException 异常。

关于 Comparable 的大部分内容也适用于 Comparator。编写 compare 方法几乎与编写 compareTo 方法相同，只是前者将两个对象作为参数传入。由于同样的原因，compare 方法必须遵守与 Comparable 的 compareTo 方法相同的四个技术限制 —— Comparator 必须对其比较的对象引入一个全序。

假设你有一个名为 Employee 的类，如下所示。

public class Employee implements Comparable<Employee> {
    public Name name()     { ... }
    public int number()    { ... }
    public Date hireDate() { ... }
       ...
}

假设 Employee 实例的自然排序是基于雇员姓名的 Name 排序（如前一个示例中定义的排序）。不幸的是，老板要求按照资历顺序列出雇员名单。这意味着我们需要做一些工作，但并不多。下面的程序将生成所需的名单。

import java.util.*;
public class EmpSort {
    static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
            public int compare(Employee e1, Employee e2) {
                return e2.hireDate().compareTo(e1.hireDate());
            }
    };

    // Employee database
    static final Collection<Employee> employees = ... ;

    public static void main(String[] args) {
        List<Employee> e = new ArrayList<Employee>(employees);
        Collections.sort(e, SENIORITY_ORDER);
        System.out.println(e);
    }
}

程序中的 Comparator 相当简单。它依赖于应用于 hireDate 访问方法返回的值的 Date 的自然排序。请注意，Comparator 将其第二个参数的雇佣日期传递给其第一个参数，而不是相反。原因是最近雇佣的员工是资历最低的；按照雇佣日期排序会按逆资历顺序排列列表。有时人们为了达到这个效果，还会使用另一种技巧，保持参数顺序，但对比较结果取反。

// 不要这样做!!
return -r1.hireDate().compareTo(r2.hireDate());

应该始终使用前一种技术，而不是后一种，因为后者不能保证正常工作。原因是compareTo方法如果其参数小于调用它的对象，则可以返回任何负int。有一个负int在取反后仍然是负数，尽管可能看起来很奇怪。

-Integer.MIN_VALUE == Integer.MIN_VALUE

前面程序中的Comparator对于对List进行排序是有效的，但它有一个缺陷：不能用于排序的集合，如TreeSet，因为它生成的排序与equals不兼容。这意味着该Comparator等同于equals方法不等同的对象。特别是，任何两个在同一日期雇佣的员工将被视为相等。当对List进行排序时，这并不重要；但当使用Comparator对排序的集合进行排序时，这是致命的。如果使用该Comparator将在同一日期雇佣的多个员工插入TreeSet中，只有第一个员工将被添加到集合中；第二个员工将被视为重复元素并被忽略。

要解决这个问题，只需调整Comparator，使其生成与equals兼容的排序。换句话说，调整它使得使用compare时只有在使用equals比较时也被视为相等的元素才被视为相等。要做到这一点，可以进行两部分比较（与Name相同），其中第一部分是我们感兴趣的部分 - 在本例中是雇佣日期 - 第二部分是唯一标识对象的属性。员工编号是明显的属性。这是结果Comparator。

static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
    public int compare(Employee e1, Employee e2) {
        int dateCmp = e2.hireDate().compareTo(e1.hireDate());
        if (dateCmp != 0)
            return dateCmp;

        return (e1.number() < e2.number() ? -1 :
               (e1.number() == e2.number() ? 0 : 1));
    }
};

最后一个注意事项：你可能会想要用简单的方式替换Comparator中的最后一个return语句：

return e1.number() - e2.number();

除非你确信没有人会有负员工编号，否则不要这样做！这个技巧在一般情况下不起作用，因为带符号的整数类型不足以表示两个任意带符号整数的差异。如果i是一个较大的正整数，j是一个较大的负整数，i - j将溢出并返回一个负整数。结果的comparator违反了我们一直在谈论的四个技术限制之一（传递性），并产生可怕而微妙的错误。这不仅仅是理论上的担忧；人们会因此受到伤害。