β

[集合框架] 对象排序

Aptusource.orgAptusource.org 186 阅读

如果有一个 List l,可以使用下面的代码进行排序:

Collections.sort(l);

如果 List 中包含了 String 类型的元素,那么,最终的结果将会按照字典顺序进行排序。如果 List 中是 Date 类型的元素,那么将会按照日期顺序进行排序。这是基于什么原理来进行排序的呢?原来 String 和 Date 都实现了 Comparable 接口,Comparable 的具体实现为类提供了自然顺序,它可以让类的实例自动进行排序。下表总结了部分 Java 平台中实现了 Comparable 接口的类:

自然顺序
Byte 有符号数
Character 无符号数
Long 有符号数
Integer 有符号数
Short 有符号数
Double 有符号数
Float 有符号数
BigInteger 有符号数
BigDecimal 有符号数
Boolean Boolean.FALSE < Boolean.TRUE
File 系统依赖的路径字典顺序
String 字典顺序
Date 时间顺序
CollationKey 特定语言的字典顺序

如果你试图对 List 排序,而 List 中的元素并没有实现 Comparable 接口,那么 Collections.sort(list) 方法将会抛出 ClassCastException 异常。同理,如果两个元素不能使用 comparator 进行比较,那么调 Collections.sort(list, comparator) 方法也会抛出 ClassCastException 异常。

编写可比较类型

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.compareTo 方法多讲一点。我们这里需要进行标准的自然排序算法,而名字中的 lastName 排序优先于 firstName 符合自然排序规则。

来看看 compartTo 方法的具体实现,首先比较了 Name 对象中最重要的部分 lastName,因为它是 String 类型,那么可以使用 String 类的比较方法(String.compareTo 按字典排序),如果比较结果不为 0,表示两个 Name 对象不相等,直接返回比较结果。如果比较结果相等,那么继续比较 firstName,最终返回 firstName 的比较结果。

下面测试一下这个类,我们创建了一组名字,并对这些名字进行排序:

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 方法有 4 个限制,具体可参看 compareTo 的 API。

比较器

如何对没有实现 Comparable 接口的对象进行排序呢?要做到这一点,可以使用 Comparator,它提供了对象的排序规则。Comparator 接口声明如下:

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

compare 方法有两个参数,返回负数、0、正数分别表示第一个参数小于、等于、大于第二个参数。如果两个参数的类型不匹配,那么 compare 方法将会抛出 ClassCastException 异常。

很多关于 Comparable 中的描述同样适合于 Comparator。编写 compare 方法和 compareTo 方法类似,不过 compare 方法是用两个参数来进行比较。

假设有个 Employee 类:

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

假设这个类的自然排序是根据 Employee 的 name 来进行排序。但是假设我们需要一份按资历排序的清单(hireDate),那么可以使用下面的代码:

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 值进行自然排序。注意,在这个例子中将第二个参数 e2 放到了前面来进行比较,这是合理的,因为雇佣时间越久的员工资历越高。你可能希望保持参数的顺序,而对结果取负数:

return -r1.hireDate().compareTo(r2.hireDate());

这种做法不可取,因为它不能保证结果的正确性。因为 compareTo 方法在进行比较的时候,可能返回任何负数。但是其中有一个负数取负值后依然是负数:

-Integer.MIN_VALUE == Integer.MIN_VALUE

上面例子中的 Comparator 可以用于对 List 排序,但是它还有一个严重的不足:它不能用于有顺序的 Collection,例如 TreeSet,因为它的排序规则和 equals 方法不兼容。意思是 Comparator 认为相等的对象,equals 方法却不认为相等。就拿上面的例子来说,如果两个员工在同一天被雇佣,那么如果是使用 List 来保存员工,就没有问题,如果是使用 TreeSet,那么第二个员工对象会被认为是重复对象被忽略。

要解决这个问题,只需要简单地修改 Comparator,使其与 equals 兼容。调整方法,让 compare 方法认为相等的对象 equals 方法也认为相对。我们把 compare 分成两部分来比较,先比较雇佣日期,如果相等再比较员工号。下面我们来看看修改后的 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));
    }
};

你可能想使用下面的算法来替换上面的 return 语句:

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

请不要这么做,除非你确定将永远不会出现负数的员工号。因为 int 的值不足以存放两个 int 相减后的结果。例如,如果 i 是一个足够大的正整数,如果 j 是一个足够小的负整数,那么 i – j 的值有可能会超出 int 能够存储的最大值的范围。这不仅是一个理论上的错误,实际上也有可能发生。

作者:Aptusource.orgAptusource.org
最好的 Java 技术博客
原文地址:[集合框架] 对象排序, 感谢原作者分享。

发表评论