java的排序和搜索

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);
  }
} ///:~

#p#分页标题#e#

通过造型为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对本身的工具举办排序。