Java中的排序

2019-11-18 13:22:15

字體：大中小

來源：轉載

供稿：網友

　　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中的Vector

下一篇：再論枚舉器