Java中的排序和搜索

2019-11-18 13:22:38

字體：大中小

來源：轉載

供稿：網友

　　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

上一篇：使用Maps

下一篇：未支持的操作