# 8.5 排序
Java 1.0和1.1庫都缺少的一樣東西是算術運算,甚至沒有最簡單的排序運算方法。因此,我們最好創建一個`Vector`,利用經典的`Quicksort`(快速排序)方法對其自身進行排序。
編寫通用的排序代碼時,面臨的一個問題是必須根據對象的實際類型來執行比較運算,從而實現正確的排序。當然,一個辦法是為每種不同的類型都寫一個不同的排序方法。然而,應認識到假若這樣做,以后增加新類型時便不易實現代碼的重復利用。
程序設計一個主要的目標就是“將發生變化的東西同保持不變的東西分隔開”。在這里,保持不變的代碼是通用的排序算法,而每次使用時都要變化的是對象的實際比較方法。因此,我們不可將比較代碼“硬編碼”到多個不同的排序例程內,而是采用“回調”技術。利用回調,經常發生變化的那部分代碼會封裝到它自己的類內,而總是保持相同的代碼則“回調”發生變化的代碼。這樣一來,不同的對象就可以表達不同的比較方式,同時向它們傳遞相同的排序代碼。
下面這個“接口”(`Interface`)展示了如何比較兩個對象,它將那些“要發生變化的東西”封裝在內:
```
//: Compare.java
// Interface for sorting callback:
package c08;
interface Compare {
boolean lessThan(Object lhs, Object rhs);
boolean lessThanOrEqual(Object lhs, Object rhs);
} ///:~
```
對這兩種方法來說,`lhs`代表本次比較中的“左手”對象,而`rhs`代表“右手”對象。
可創建`Vector`的一個子類,通過`Compare`實現“快速排序”。對于這種算法,包括它的速度以及原理等等,在此不具體說明。欲知詳情,可參考Binstock和Rex編著的《Practical Algorithms for Programmers》,由Addison-Wesley于1995年出版。
```
//: SortVector.java
// A generic sorting vector
package c08;
import java.util.*;
public class SortVector extends Vector {
private Compare compare; // To hold the callback
public SortVector(Compare comp) {
compare = comp;
}
public void sort() {
quickSort(0, size() - 1);
}
private void quickSort(int left, int right) {
if(right > left) {
Object o1 = elementAt(right);
int i = left - 1;
int j = right;
while(true) {
while(compare.lessThan(
elementAt(++i), o1))
;
while(j > 0)
if(compare.lessThanOrEqual(
elementAt(--j), o1))
break; // out of while
if(i >= j) break;
swap(i, j);
}
swap(i , right);
quickSort(left, i-1);
quickSort(i+1, right);
}
}
private void swap(int loc1, int loc2) {
Object tmp = elementAt(loc1);
setElementAt(elementAt(loc2), loc1);
setElementAt(tmp, loc2);
}
} ///:~
```
現在,大家可以明白“回調”一詞的來歷,這是由于`quickSort()`方法“往回調用”了`Compare`中的方法。從中亦可理解這種技術如何生成通用的、可重復利用(復用)的代碼。
為使用`SortVector`,必須創建一個類,令其為我們準備排序的對象實現`Compare`。此時內部類并不顯得特別重要,但對于代碼的組織卻是有益的。下面是針對`String`對象的一個例子:
```
//: StringSortTest.java
// Testing the generic sorting Vector
package c08;
import java.util.*;
public class StringSortTest {
static class StringCompare implements Compare {
public boolean lessThan(Object l, Object r) {
return ((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) < 0;
}
public boolean
lessThanOrEqual(Object l, Object r) {
return ((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) <= 0;
}
}
public static void main(String[] args) {
SortVector sv =
new SortVector(new StringCompare());
sv.addElement("d");
sv.addElement("A");
sv.addElement("C");
sv.addElement("c");
sv.addElement("b");
sv.addElement("B");
sv.addElement("D");
sv.addElement("a");
sv.sort();
Enumeration e = sv.elements();
while(e.hasMoreElements())
System.out.println(e.nextElement());
}
} ///:~
```
內部類是“靜態”(`Static`)的,因為它毋需連接一個外部類即可工作。
大家可以看到,一旦設置好框架,就可以非常方便地重復使用象這樣的一個設計——只需簡單地寫一個類,將“需要發生變化”的東西封裝進去,然后將一個對象傳給`SortVector`即可。
比較時將字符串強制為小寫形式,所以大寫`A`會排列于小寫`a`的旁邊,而不會移動一個完全不同的地方。然而,該例也顯示了這種方法的一個不足,因為上述測試代碼按照出現順序排列同一個字母的大寫和小寫形式:`A a b B c C d D`。但這通常不是一個大問題,因為經常處理的都是更長的字符串,所以上述效果不會顯露出來(Java 1.2的集合提供了排序功能,已解決了這個問題)。
繼承(`extends`)在這兒用于創建一種新類型的`Vector`——也就是說,`SortVector`屬于一種`Vector`,并帶有一些附加的功能。繼承在這里可發揮很大的作用,但了帶來了問題。它使一些方法具有了`final`屬性(已在第7章講述),所以不能覆蓋它們。如果想創建一個排好序的`Vector`,令其只接收和生成`String`對象,就會遇到麻煩。因為`addElement()`和`elementAt()`都具有`final`屬性,而且它們都是我們必須覆蓋的方法,否則便無法實現只能接收和產生`String`對象。
但在另一方面,請考慮采用“組合”方法:將一個對象置入一個新類的內部。此時,不是改寫上述代碼來達到這個目的,而是在新類里簡單地使用一個`SortVector`。在這種情況下,用于實現`Compare`接口的內部類就可以“匿名”地創建。如下所示:
```
//: StrSortVector.java
// Automatically sorted Vector that
// accepts and produces only Strings
package c08;
import java.util.*;
public class StrSortVector {
private SortVector v = new SortVector(
// Anonymous inner class:
new Compare() {
public boolean
lessThan(Object l, Object r) {
return
((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) < 0;
}
public boolean
lessThanOrEqual(Object l, Object r) {
return
((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) <= 0;
}
}
);
private boolean sorted = false;
public void addElement(String s) {
v.addElement(s);
sorted = false;
}
public String elementAt(int index) {
if(!sorted) {
v.sort();
sorted = true;
}
return (String)v.elementAt(index);
}
public Enumeration elements() {
if(!sorted) {
v.sort();
sorted = true;
}
return v.elements();
}
// Test it:
public static void main(String[] args) {
StrSortVector sv = new StrSortVector();
sv.addElement("d");
sv.addElement("A");
sv.addElement("C");
sv.addElement("c");
sv.addElement("b");
sv.addElement("B");
sv.addElement("D");
sv.addElement("a");
Enumeration e = sv.elements();
while(e.hasMoreElements())
System.out.println(e.nextElement());
}
} ///:~
```
這樣便可快速復用來自`SortVector`的代碼,從而獲得希望的功能。然而,并不是來自`SortVector`和`Vector`的所有`public`方法都能在`StrSortVector`中出現。若按這種形式復用代碼,可在新類里為包含類內的每一個方法都生成一個定義。當然,也可以在剛開始時只添加少數幾個,以后根據需要再添加更多的。新類的設計最終會穩定下來。
這種方法的好處在于它仍然只接納`String`對象,也只產生`String`對象。而且相應的檢查是在編譯期間進行的,而非在運行期。當然,只有`addElement()`和`elementAt()`才具備這一特性;`elements()`仍然會產生一個`Enumeration`(枚舉),它在編譯期的類型是未定的。當然,對`Enumeration`以及在`StrSortVector`中的類型檢查會照舊進行;如果真的有什么錯誤,運行期間會簡單地產生一個異常。事實上,我們在編譯或運行期間能保證一切都正確無誤嗎?(也就是說,“代碼測試時也許不能保證”,以及“該程序的用戶有可能做一些未經我們測試的事情”)。盡管存在其他選擇和爭論,使用繼承都要容易得多,只是在轉換時讓人深感不便。同樣地,一旦為Java加入參數化類型,就有望解決這個問題。
大家在這個類中可以看到有一個名為`sorted`的標志。每次調用`addElement()`時,都可對`Vector`進行排序,而且將其連續保持在一個排好序的狀態。但在開始讀取之前,人們總是向一個`Vector`添加大量元素。所以與其在每個`addElement()`后排序,不如一直等到有人想讀取`Vector`,再對其進行排序。后者的效率要高得多。這種除非絕對必要,否則就不采取行動的方法叫作“懶惰求值”(還有一種類似的技術叫作“懶惰初始化”——除非真的需要一個字段值,否則不進行初始化)。
- Java 編程思想
- 寫在前面的話
- 引言
- 第1章 對象入門
- 1.1 抽象的進步
- 1.2 對象的接口
- 1.3 實現方案的隱藏
- 1.4 方案的重復使用
- 1.5 繼承:重新使用接口
- 1.6 多態對象的互換使用
- 1.7 對象的創建和存在時間
- 1.8 異常控制:解決錯誤
- 1.9 多線程
- 1.10 永久性
- 1.11 Java和因特網
- 1.12 分析和設計
- 1.13 Java還是C++
- 第2章 一切都是對象
- 2.1 用引用操縱對象
- 2.2 所有對象都必須創建
- 2.3 絕對不要清除對象
- 2.4 新建數據類型:類
- 2.5 方法、參數和返回值
- 2.6 構建Java程序
- 2.7 我們的第一個Java程序
- 2.8 注釋和嵌入文檔
- 2.9 編碼樣式
- 2.10 總結
- 2.11 練習
- 第3章 控制程序流程
- 3.1 使用Java運算符
- 3.2 執行控制
- 3.3 總結
- 3.4 練習
- 第4章 初始化和清除
- 4.1 用構造器自動初始化
- 4.2 方法重載
- 4.3 清除:收尾和垃圾收集
- 4.4 成員初始化
- 4.5 數組初始化
- 4.6 總結
- 4.7 練習
- 第5章 隱藏實現過程
- 5.1 包:庫單元
- 5.2 Java訪問指示符
- 5.3 接口與實現
- 5.4 類訪問
- 5.5 總結
- 5.6 練習
- 第6章 類復用
- 6.1 組合的語法
- 6.2 繼承的語法
- 6.3 組合與繼承的結合
- 6.4 到底選擇組合還是繼承
- 6.5 protected
- 6.6 累積開發
- 6.7 向上轉換
- 6.8 final關鍵字
- 6.9 初始化和類裝載
- 6.10 總結
- 6.11 練習
- 第7章 多態性
- 7.1 向上轉換
- 7.2 深入理解
- 7.3 覆蓋與重載
- 7.4 抽象類和方法
- 7.5 接口
- 7.6 內部類
- 7.7 構造器和多態性
- 7.8 通過繼承進行設計
- 7.9 總結
- 7.10 練習
- 第8章 對象的容納
- 8.1 數組
- 8.2 集合
- 8.3 枚舉器(迭代器)
- 8.4 集合的類型
- 8.5 排序
- 8.6 通用集合庫
- 8.7 新集合
- 8.8 總結
- 8.9 練習
- 第9章 異常差錯控制
- 9.1 基本異常
- 9.2 異常的捕獲
- 9.3 標準Java異常
- 9.4 創建自己的異常
- 9.5 異常的限制
- 9.6 用finally清除
- 9.7 構造器
- 9.8 異常匹配
- 9.9 總結
- 9.10 練習
- 第10章 Java IO系統
- 10.1 輸入和輸出
- 10.2 增添屬性和有用的接口
- 10.3 本身的缺陷:RandomAccessFile
- 10.4 File類
- 10.5 IO流的典型應用
- 10.6 StreamTokenizer
- 10.7 Java 1.1的IO流
- 10.8 壓縮
- 10.9 對象序列化
- 10.10 總結
- 10.11 練習
- 第11章 運行期類型識別
- 11.1 對RTTI的需要
- 11.2 RTTI語法
- 11.3 反射:運行期類信息
- 11.4 總結
- 11.5 練習
- 第12章 傳遞和返回對象
- 12.1 傳遞引用
- 12.2 制作本地副本
- 12.3 克隆的控制
- 12.4 只讀類
- 12.5 總結
- 12.6 練習
- 第13章 創建窗口和程序片
- 13.1 為何要用AWT?
- 13.2 基本程序片
- 13.3 制作按鈕
- 13.4 捕獲事件
- 13.5 文本字段
- 13.6 文本區域
- 13.7 標簽
- 13.8 復選框
- 13.9 單選鈕
- 13.10 下拉列表
- 13.11 列表框
- 13.12 布局的控制
- 13.13 action的替代品
- 13.14 程序片的局限
- 13.15 視窗化應用
- 13.16 新型AWT
- 13.17 Java 1.1用戶接口API
- 13.18 可視編程和Beans
- 13.19 Swing入門
- 13.20 總結
- 13.21 練習
- 第14章 多線程
- 14.1 反應靈敏的用戶界面
- 14.2 共享有限的資源
- 14.3 堵塞
- 14.4 優先級
- 14.5 回顧runnable
- 14.6 總結
- 14.7 練習
- 第15章 網絡編程
- 15.1 機器的標識
- 15.2 套接字
- 15.3 服務多個客戶
- 15.4 數據報
- 15.5 一個Web應用
- 15.6 Java與CGI的溝通
- 15.7 用JDBC連接數據庫
- 15.8 遠程方法
- 15.9 總結
- 15.10 練習
- 第16章 設計模式
- 16.1 模式的概念
- 16.2 觀察器模式
- 16.3 模擬垃圾回收站
- 16.4 改進設計
- 16.5 抽象的應用
- 16.6 多重分發
- 16.7 訪問器模式
- 16.8 RTTI真的有害嗎
- 16.9 總結
- 16.10 練習
- 第17章 項目
- 17.1 文字處理
- 17.2 方法查找工具
- 17.3 復雜性理論
- 17.4 總結
- 17.5 練習
- 附錄A 使用非JAVA代碼
- 附錄B 對比C++和Java
- 附錄C Java編程規則
- 附錄D 性能
- 附錄E 關于垃圾收集的一些話
- 附錄F 推薦讀物