共计 5439 个字符，预计需要花费 14 分钟才能阅读完成。
对象排序
List l 可以如下排序。
Collections.sort(l);
如果 List 包含 String 元素，它将按字母顺序排序，如果它由 Date 元素组成，它将按时间顺序排序，这是怎么发生的？String 和 Date 都实现了 Comparable 接口，Comparable 实现为类提供了自然的顺序，允许该类的对象自动排序，下表总结了一些实现 Comparable 的更重要的 Java 平台类。
类
自然排序
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 类型
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 对象是不可变的，在所有其他条件相同的情况下，不可变类型是解决问题的方法，特别是对于将作为集合中的元素或 Map 中的键使用的对象，如果你在集合中修改元素或键，这些集合将会中断。
构造函数检查其参数是否为 null，这可以确保所有 Name 对象都格式正确，这样其他任何方法都不会抛出 NullPointerException。
hashCode 方法被重新定义，这对于重新定义 equals 方法的任何类都是必不可少的（等同对象必须具有相同的哈希码）。
如果指定的对象为 null 或类型不合适，则 equals 方法返回 false，compareTo 方法在这些情况下抛出运行时异常，这两种行为都是各自方法的一般契约所要求的。
toString 方法已重新定义，因此它以人类可读的形式打印 Name，这总是一个好主意，特别是对于要放入集合的对象，各种集合类型的 toString 方法依赖于其元素、键和值的 toString 方法。
由于本节是关于元素排序的，让我们再谈谈 Name 的 compareTo 方法，它实现了标准的名称排序算法，其中姓氏优先于名字，这正是你想要的自然顺序，如果自然顺序不自然，那将会非常混乱！
看看 compareTo 是如何实现的，因为它非常经典，首先，比较对象的最重要部分（在本例中为姓氏），通常，你可以只使用部分类型的自然顺序，在这种情况下，该部分是一个字符串，自然（词典）排序正是所要求的。如果比较的结果不是 0（代表相等），那么就完成了：你只需返回结果。如果最重要的部分相同，则继续比较下一个最重要的部分，在这种情况下，只有两个部分 — 名字和姓氏。如果有更多的部分，你会以明显的方式进行，比较部分，直到你发现两个不相等或你正在比较最不重要的部分，此时你将返回比较的结果。
为了说明这一切都是有效的，这里有一个程序，它构建了一个名称列表并对它们进行排序。
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 的文档。尝试对违反限制的对象列表进行排序具有未定义的行为，从技术上讲，这些限制确保自然顺序是实现它的类的对象的总顺序，这对于确保明确定义排序是必要的。
Comparators
如果你想按一些对象的自然顺序以外的顺序排序，该怎么办？或者，如果要对某些未实现 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 将第二个参数的雇用日期传递给第一个参数，而不是反过来，原因是最近招聘的员工级别最低，按雇用日期顺序排序会使该名单的资历顺序相反，人们有时用来达到这种效果的另一种技术是保持参数顺序，但要否定比较的结果。
// Don’t do this!!
return -r1.hireDate().compareTo(r2.hireDate());
你应该总是使用前一种技术来支持后者，因为后者不能保证有效，这样做的原因是 compareTo 方法可以返回任何负整数，如果它的参数小于调用它的对象。有一个负整型数在被否定时仍然是负的，尽管这看起来很奇怪。
-Integer.MIN_VALUE == Integer.MIN_VALUE
上一个程序中的 Comparator 可以很好地对 List 进行排序，但确实存在一个缺陷：它不能用于排序已排序的集合，例如 TreeSet，因为它生成的顺序与 equals 不兼容，这意味着这个 Comparator 相当于 equals 方法所没有的对象。特别是，在同一天雇佣的任何两名员工将相等，当你对 List 进行排序时，这并不重要，但是当你使用 Comparator 来排序一个已排序的集合时，它是致命的，如果你使用此 Comparator 将在同一日期雇用的多名员工插入到 TreeSet 中，则只会将第一个员工添加到该集合中，第二个将被视为重复元素，将被忽略。
要解决此问题，只需调整 Comparator，以便生成与 equals 兼容的排序，换句话说，调整它以便在使用 compare 时看到相同的唯一元素是那些在使用 equals 进行比较时也被视为相等的元素。执行此操作的方法是执行两部分比较（像对于 Name），其中第一部分是我们感兴趣的部分 — 在这种情况下，是雇用日期 — 第二部分是唯一标识对象的属性，员工编号在这里是明显的属性，这是比较器的结果。
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 违反了我们一直在讨论的四个技术限制之一（传递性）并产生可怕的、微妙的错误，这不是纯粹的理论问题。
上一篇：Map 接口