熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> JSP教程 >> 正文

Java中的排序和搜索

2022-06-13   來源: JSP教程 

  Java 添加了自己的一套實用工具可用來對數組或列表進行排列和搜索這些工具都屬於兩個新類的靜態方法這兩個類分別是用於排序和搜索數組的Arrays以及用於排序和搜索列表的Collections
  
   數組
  
  Arrays類為所有基本數據類型的數組提供了一個過載的sort()和binarySearch()它們亦可用於String和Object下面這個例子顯示出如何排序和搜索一個字節數組(其他所有基本數據類型都是類似的)以及一個String數組
  
  //: Arrayjava
  // Testing the sorting & searching in Arrays
  package cnewcollections;
  import javautil*;
  
  public class Array {
   static Random r = new Random();
   static String ssource =
    ABCDEFGHIJKLMNOPQRSTUVWXYZ +
    abcdefghijklmnopqrstuvwxyz;
   static char[] src = ssourcetoCharArray();
   // Create a random String
   public static String randString(int length) {
    char[] buf = new char[length];
    int rnd;
    for(int i = ; 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);
   }
  } ///:~
  
  類的第一部分包含了用於產生隨機字串對象的實用工具,可供選擇的隨機字母保存在一個字符數組中。tw.WINgwIT.cOMrandString()返回一個任意長度的字串;而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 pareTo(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對象——運行期系統會捕獲任何差錯。將兩個字串都強迫換成小寫形式後,pareTo()方法會產生預期的結果。
  若用自己的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
From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19495.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.