Java
Arrays類為所有基本數據類型的數組提供了一個過載的sort()和binarySearch()
//: Array
// Testing the sorting & searching in Arrays
package c
import java
public class Array
static Random r = new Random();
static String ssource =
static char[] src = ssource
// Create a random String
public static String randString(int length) {
char[] buf = new char[length];
int rnd;
for(int 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