Question

Java 1.2 添加了自己的一套实用工具，可用来对数组或列表进行排列和搜索。这些工具都属于两个新类的“静态”方法。这两个类分别是用于排序和搜索数组的 Arrays，以及用于排序和搜索列表的 Collections。

1. 数组

Arrays 类为所有基本数据类型的数组提供了一个过载的 sort() 和 binarySearch()，它们亦可用于 String 和 Object。下面这个例子显示出如何排序和搜索一个字节数组（其他所有基本数据类型都是类似的）以及一个 String 数组：

//: Array1.java
// Testing the sorting & searching in Arrays
package c08.newcollections;
import java.util.*;

public class Array1 {
  static Random r = new Random();
  static String ssource = 
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
    "abcdefghijklmnopqrstuvwxyz";
  static char[] src = ssource.toCharArray();
  // Create a random String
  public static String randString(int length) {
    char[] buf = new char[length];
    int rnd;
    for(int i = 0; i < length; i++) {
      rnd = Math.abs(r.nextInt()) % src.length;
      buf[i] = src[rnd];
    }
    return new String(buf);
  }
  // Create a random array of Strings:
  public static 
  String[] randStrings(int length, int size) {
    String[] s = new String[size];
    for(int i = 0; i < size; i++)
      s[i] = randString(length);
    return s;
  }
  public static void print(byte[] b) {
    for(int i = 0; i < b.length; i++)
      System.out.print(b[i] + " ");
    System.out.println();
  }
  public static void print(String[] s) {
    for(int i = 0; i < s.length; i++)
      System.out.print(s[i] + " ");
    System.out.println();
  }
  public static void main(String[] args) {
    byte[] b = new byte[15];
    r.nextBytes(b); // Fill with random bytes
    print(b);
    Arrays.sort(b);
    print(b);
    int loc = Arrays.binarySearch(b, b[10]);
    System.out.println("Location of " + b[10] +
      " = " + loc);
    // Test String sort & search:
    String[] s = randStrings(4, 10);
    print(s);
    Arrays.sort(s);
    print(s);
    loc = Arrays.binarySearch(s, s[4]);
    System.out.println("Location of " + s[4] +
      " = " + loc);
  }
} ///:~

类的第一部分包含了用于产生随机字串对象的实用工具，可供选择的随机字母保存在一个字符数组中。randString() 返回一个任意长度的字串；而 readStrings() 创建随机字串的一个数组，同时给定每个字串的长度以及希望的数组大小。两个 print() 方法简化了对示范数组的显示。在 main() 中，Random.nextBytes() 用随机选择的字节填充数组自变量（没有对应的 Random 方法用于创建其他基本数据类型的数组）。获得一个数组后，便可发现为了执行 sort() 或者 binarySearch()，只需发出一次方法调用即可。与 binarySearch() 有关的还有一个重要的警告：若在执行一次 binarySearch() 之前不调用 sort()，便会发生不可预测的行为，其中甚至包括无限循环。

对 String 的排序以及搜索是相似的，但在运行程序的时候，我们会注意到一个有趣的现象：排序遵守的是字典顺序，亦即大写字母在字符集中位于小写字母的前面。因此，所有大写字母都位于列表的最前面，后面再跟上小写字母——Z 居然位于 a 的前面。似乎连电话簿也是这样排序的。

2. 可比较与比较器

但假若我们不满足这一排序方式，又该如何处理呢？例如本书后面的索引，如果必须对以 A 或 a 开头的词条分别到两处地方查看，那么肯定会使读者颇不耐烦。

若想对一个 Object 数组进行排序，那么必须解决一个问题。根据什么来判定两个 Object 的顺序呢？不幸的是，最初的 Java 设计者并不认为这是一个重要的问题，否则就已经在根类 Object 里定义它了。这样造成的一个后果便是：必须从外部进行 Object 的排序，而且新的集合库提供了实现这一操作的标准方式（最理想的是在 Object 里定义它）。

针对 Object 数组（以及 String，它当然属于 Object 的一种），可使用一个 sort()，并令其接纳另一个参数：实现了 Comparator 接口（即“比较器”接口，新集合库的一部分）的一个对象，并用它的单个 compare() 方法进行比较。这个方法将两个准备比较的对象作为自己的参数使用——若第一个参数小于第二个，返回一个负整数；若相等，返回零；若第一个参数大于第二个，则返回正整数。基于这一规则，上述例子的 String 部分便可重新写过，令其进行真正按字母顺序的排序：

//: AlphaComp.java
// Using Comparator to perform an alphabetic sort
package c08.newcollections;
import java.util.*;

public class AlphaComp implements Comparator {
  public int compare(Object o1, Object o2) {
    // Assume it's used only for Strings...
    String s1 = ((String)o1).toLowerCase();
    String s2 = ((String)o2).toLowerCase();
    return s1.compareTo(s2);
  }
  public static void main(String[] args) {
    String[] s = Array1.randStrings(4, 10);
    Array1.print(s);
    AlphaComp ac = new AlphaComp();
    Arrays.sort(s, ac);
    Array1.print(s);
    // Must use the Comparator to search, also:
    int loc = Arrays.binarySearch(s, s[3], ac);
    System.out.println("Location of " + s[3] +
     " = " + loc);
  }
} ///:~

通过造型为 String，compare() 方法会进行“暗示”性的测试，保证自己操作的只能是 String 对象——运行期系统会捕获任何差错。将两个字串都强迫换成小写形式后，String.compareTo() 方法会产生预期的结果。

若用自己的 Comparator 来进行一次 sort()，那么在使用 binarySearch() 时必须使用那个相同的 Comparator。

Arrays 类提供了另一个 sort() 方法，它会采用单个自变量：一个 Object 数组，但没有 Comparator。这个 sort() 方法也必须用同样的方式来比较两个 Object。通过实现 Comparable 接口，它采用了赋予一个类的“自然比较方法”。这个接口含有单独一个方法——compareTo()，能分别根据它小于、等于或者大于自变量而返回负数、零或者正数，从而实现对象的比较。下面这个例子简单地阐示了这一点：

//: CompClass.java
// A class that implements Comparable
package c08.newcollections;
import java.util.*;

public class CompClass implements Comparable {
  private int i;
  public CompClass(int ii) { i = ii; }
  public int compareTo(Object o) {
    // Implicitly tests for correct type:
    int argi = ((CompClass)o).i;
    if(i == argi) return 0;
    if(i < argi) return -1;
    return 1;
  }
  public static void print(Object[] a) {
    for(int i = 0; i < a.length; i++)
      System.out.print(a[i] + " ");
    System.out.println();
  }
  public String toString() { return i + ""; }
  public static void main(String[] args) {
    CompClass[] a = new CompClass[20];
    for(int i = 0; i < a.length; i++)
      a[i] = new CompClass(
        (int)(Math.random() *100));
    print(a);
    Arrays.sort(a);
    print(a);
    int loc = Arrays.binarySearch(a, a[3]);
    System.out.println("Location of " + a[3] +
     " = " + loc);
  }
} ///:~

当然，我们的 compareTo() 方法亦可根据实际情况增大复杂程度。

3. 列表

可用与数组相同的形式排序和搜索一个列表（List）。用于排序和搜索列表的静态方法包含在类 Collections 中，但它们拥有与 Arrays 中差不多的签名：sort(List) 用于对一个实现了 Comparable 的对象列表进行排序；binarySearch(List,Object) 用于查找列表中的某个对象；sort(List,Comparator) 利用一个“比较器”对一个列表进行排序；而 binarySearch(List,Object,Comparator) 则用于查找那个列表中的一个对象（注释⑨）。下面这个例子利用了预先定义好的 CompClass 和 AlphaComp 来示范 Collections 中的各种排序工具：

//: ListSort.java
// Sorting and searching Lists with 'Collections'
package c08.newcollections;
import java.util.*;

public class ListSort {
  public static void main(String[] args) {
    final int SZ = 20;
    // Using "natural comparison method":
    List a = new ArrayList();
    for(int i = 0; i < SZ; i++)
      a.add(new CompClass(
        (int)(Math.random() *100)));
    Collection1.print(a);
    Collections.sort(a);
    Collection1.print(a);
    Object find = a.get(SZ/2);
    int loc = Collections.binarySearch(a, find);
    System.out.println("Location of " + find +
     " = " + loc);
    // Using a Comparator:
    List b = new ArrayList();
    for(int i = 0; i < SZ; i++)
      b.add(Array1.randString(4));
    Collection1.print(b);
    AlphaComp ac = new AlphaComp();
    Collections.sort(b, ac);
    Collection1.print(b);
    find = b.get(SZ/2);
    // Must use the Comparator to search, also:
    loc = Collections.binarySearch(b, find, ac);
    System.out.println("Location of " + find +
     " = " + loc);
  }
} ///:~ 

⑨：在本书写作时，已宣布了一个新的 Collections.stableSort()，可用它进行合并式排序，但还没有它的测试版问世。

这些方法的用法与在 Arrays 中的用法是完全一致的，只是用一个列表代替了数组。

TreeMap 也必须根据 Comparable 或者 Comparator 对自己的对象进行排序。