WEB开发网
开发学院WEB开发Jsp Java中的排序和搜索 阅读

Java中的排序和搜索

 2008-01-05 09:51:07 来源:WEB开发网   
核心提示:java 1.2添加了自己的一套实用工具,可用来对数组或列表进行排列和搜索,Java中的排序和搜索,这些工具都属于两个新类的“静态”方法,这两个类分别是用于排序和搜索数组的Arrays,3. 列表可用与数组相同的形式排序和搜索一个列表(List),用于排序和搜索列表的静态方法包含在类Collections中,以及用于排

  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.a

Tags:Java 排序 搜索

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接