# 对象排序

> 原文： [https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html](https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html)

`List` `l`可以如下排序。

```
Collections.sort(l);

```

如果`List`由`String`元素组成，它将按字母顺序排序。如果它由`Date`元素组成，它将按时间顺序排序。这是怎么发生的？ `String`和`Date`均实现 [`Comparable`](https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html) 接口。 `Comparable`实现为类提供 _ 自然排序 _，允许该类的对象自动排序。 下表总结了一些实现`Comparable`的更重要的 Java 平台类。

**Classes Implementing Comparable**
| 类 | 自然排序 |
| --- | --- |
| `Byte` | 签名数字 |
| `Character` | 无符号数字 |
| `Long` | 签名数字 |
| `Integer` | 签名数字 |
| `Short` | 签名数字 |
| `Double` | 签名数字 |
| `Float` | 签名数字 |
| `BigInteger` | 签名数字 |
| `BigDecimal` | 签名数字 |
| `Boolean` | `Boolean.FALSE < Boolean.TRUE` |
| `File` | 路径名称上依赖于系统的词典 |
| `String` | 辞书 |
| `Date` | 年代 |
| `CollationKey` | 特定于区域设置的词典 |

如果您尝试对列表进行排序，其中未实现`Comparable`，`Collections.sort(list)`的元素将抛出 [`ClassCastException`](https://docs.oracle.com/javase/8/docs/api/java/lang/ClassCastException.html) 。类似地，如果您尝试使用`comparator`对其元素无法相互比较的列表进行排序，`Collections.sort(list, comparator)`将抛出`ClassCastException`。可以相互比较的元素称为 _ 相互比较 _。虽然不同类型的元素可以相互比较，但这里列出的类别都不允许进行类间比较。

如果您只想对可比元素的列表进行排序或创建它们的已排序集合，那么您真正需要了解`Comparable`接口。如果您想要实现自己的`Comparable`类型，下一部分将是您感兴趣的。

## 编写自己的可比类型

`Comparable`接口由以下方法组成。

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

```

`compareTo`方法将接收对象与指定对象进行比较，并返回负整数 0 或正整数，具体取决于接收对象是否小于，等于或大于指定对象。如果无法将指定的对象与接收对象进行比较，则该方法将抛出`ClassCastException`。

[`following class representing a person's name`](examples/Name.java) 实现`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`方法的任何类都是必不可少的。 （等于对象必须具有相同的哈希码。）
*   如果指定的对象是`null`或类型不合适，`equals`方法将返回`false`。在这些情况下，`compareTo`方法会抛出运行时异常。这些行为都是各方法的一般合同所要求的。
*   `toString`方法已重新定义，因此它以人类可读的形式打印`Name`。这总是一个好主意，特别是对于要放入集合的对象。各种集合类型的`toString`方法依赖于元素，键和值的`toString`方法。

由于本节是关于元素排序的，让我们再谈谈`Name`的`compareTo`方法。它实现了标准的名称排序算法，其中姓氏优先于名字。这正是您想要的自然顺序。如果自然顺序不自然，那将会非常混乱！

看看`compareTo`是如何实现的，因为它非常典型。首先，比较对象的最重要部分（在本例中为姓氏）。通常，您可以使用零件类型的自然顺序。在这种情况下，该部分是`String`，自然（词典）排序正是所要求的。如果比较结果为零，表示相等，那么您就完成了：您只需返回结果。如果最重要的部分相同，则继续比较下一个最重要的部分。在这种情况下，只有两个部分 - 名字和姓氏。如果有更多的零件，你会以明显的方式进行，比较零件，直到你发现两个不相等或你正在比较最不重要的部分，此时你将返回比较的结果。

只是为了表明一切正常，这里是 [`a program that builds a list of names and sorts them`](examples/NameSort.java) 。

```
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`的对象进行排序，该怎么办？要做这些事情中的任何一个，你需要提供一个 [`Comparator`](https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html) - 一个封装排序的对象。与`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`相当简单。它依赖于`Date`应用于`hireDate`存取方法返回的值的自然顺序。请注意，`Comparator`将其第二个参数的雇用日期传递给第一个参数，而不是相反。原因是最近雇用的员工是最不高级的;按雇用日期顺序排序会使列表按反向资历顺序排列。人们有时用来实现这种效果的另一种技术是维持参数顺序但是否定比较的结果。

```
// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());

```

你应该总是使用前一种技术来支持后者，因为后者不能保证工作。原因是如果`compareTo`方法的参数小于调用它的对象，`compareTo`方法可以返回任何负数`int`。有一个负面`int`在否定时仍然是负面的，看起来很奇怪。

```
-Integer.MIN_VALUE == Integer.MIN_VALUE

```

前面程序中的`Comparator`适用于排序`List`，但它有一个缺陷：它不能用于排序已排序的集合，例如`TreeSet`，因为它生成的顺序是 _ 与 _ 等于不兼容。这意味着这个`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`违反了我们一直在讨论的四个技术限制之一（传递性）并产生可怕的，微妙的错误。这不是纯粹的理论问题;人们被它烧了。