Java中的排序

　　Java 和庫都缺少的一樣東西是算術運算甚至沒有最簡單的排序運算方法因此我們最好創建一個Vector利用經典的Quicksort（快速排序）方法對其自身進行排序
　　編寫通用的排序代碼時面臨的一個問題是必須根據對象的實際類型來執行比較運算從而實現正確的排序當然一個辦法是為每種不同的類型都寫一個不同的排序方法然而應認識到假若這樣做以後增加新類型時便不易實現代碼的重復利用
　　程序設計一個主要的目標就是將發生變化的東西同保持不變的東西分隔開在這裡保持不變的代碼是通用的排序算法而每次使用時都要變化的是對象的實際比較方法因此我們不可將比較代碼硬編碼到多個不同的排序例程內而是采用回調技術利用回調經常發生變化的那部分代碼會封裝到它自己的類內而總是保持相同的代碼則回調發生變化的代碼這樣一來不同的對象就可以表達不同的比較方式同時向它們傳遞相同的排序代碼
　　下面這個接口（Interface）展示了如何比較兩個對象它將那些要發生變化的東西封裝在內
　　
　　//: Comparejava
　　// Interface for sorting callback:
　　package c;
　　
　　interface Compare {
　　　boolean lessThan(Object lhs Object rhs);
　　　boolean lessThanOrEqual(Object lhs Object rhs);
　　} ///:~
　　
　　對這兩種方法來說lhs代表本次比較中的左手對象而rhs代表右手對象
　　可創建Vector的一個子類通過Compare實現快速排序對於這種算法包括它的速度以及原理等等在此不具體說明欲知詳情可參考Binstock和Rex編著的《Practical Algorithms for Programmers》由AddisonWesley於年出版
　　
　　//: SortVectorjava
　　// A generic sorting vector
　　package c;
　　import javautil*;
　　
　　public class SortVector extends Vector {
　　　private Compare compare; // To hold the callback
　　　public SortVector(Compare comp) {
　　　　compare = comp;
　　　}
　　　public void sort() {
　　　　quickSort( size() );
　　　}
　　　private void quickSort(int left int right) {
　　　　if(right > left) {
　　　　　Object o = elementAt(right);
　　　　　int i = left ;
　　　　　int j = right;
　　　　　while(true) {
　　　　　　while(comparelessThan(
　　　　　　　　　elementAt(++i) o))
　　　　　　　;
　　　　　　while(j > )
　　　　　　　if(comparelessThanOrEqual(
　　　　　　　　 elementAt(j) o))
　　　　　　　　break; // out of while
　　　　　　if(i >= j) break;
　　　　　　swap(i j);
　　　　　}
　　　　　swap(i right);
　　　　　quickSort(left i);
　　　　　quickSort(i+ right);
　　　　}
　　　}
　　　private void swap(int loc int loc) {
　　　　Object tmp = elementAt(loc);
　　　　setElementAt(elementAt(loc) loc);
　　　　setElementAt(tmp loc);
　　　}
　　} ///:~
　　
　　現在大家可以明白回調一詞的來歷這是由於quickSort()方法往回調用了Compare中的方法從中亦可理解這種技術如何生成通用的可重復利用（再生）的代碼
　　為使用SortVector必須創建一個類令其為我們准備排序的對象實現Compare此時內部類並不顯得特別重要但對於代碼的組織卻是有益的下面是針對String對象的一個例子
　　
　　//: StringSortTestjava
　　// Testing the generic sorting Vector
　　package c;
　　import javautil*;
　　
　　public class StringSortTest {
　　　static class StringCompare implements Compare {
　　　　public boolean lessThan(Object l Object r) {
　　　　　return ((String)l)toLowerCase(pareTo(
　　　　　　((String)r)toLowerCase()) < ;
　　　　}
　　　　public boolean
　　　　lessThanOrEqual(Object l Object r) {
　　　　　return ((String)l)toLowerCase(pareTo(
　　　　　　((String)r)toLowerCase()) <= ;
　　　　}
　　　}
　　　public static void main(String[] args) {
　　　　SortVector sv =
　　　　　new SortVector(new StringCompare());
　　　　svaddElement(d);
　　　　svaddElement(A);
　　　　svaddElement(C);
　　　　svaddElement(c);
　　　　svaddElement(b);
　　　　svaddElement(B);
　　　　svaddElement(D);
　　　　svaddElement(a);
　　　　svsort();
　　　　Enumeration e = svelements();
　　　　while(ehasMoreElements())
　　　　　Systemoutprintln(enextElement());
　　　}
　　} ///:~
　　
　　內部類是靜態（Static）的因為它毋需連接一個外部類即可工作
　　大家可以看到一旦設置好框架就可以非常方便地重復使用象這樣的一個設計——只需簡單地寫一個類將需要發生變化的東西封裝進去然後將一個對象傳給SortVector即可
　　比較時將字串強制為小寫形式所以大寫A會排列於小寫a的旁邊而不會移動一個完全不同的地方然而該例也顯示了這種方法的一個不足因為上述測試代碼按照出現順序排列同一個字母的大寫和小寫形式A a b B c C d D但這通常不是一個大問題因為經常處理的都是更長的字串所以上述效果不會顯露出來（Java 的集合提供了排序功能已解決了這個問題）
　　繼承（extends）在這兒用於創建一種新類型的Vector——也就是說SortVector屬於一種Vector並帶有一些附加的功能繼承在這裡可發揮很大的作用但了帶來了問題它使一些方法具有了final屬性（已在第章講述）所以不能覆蓋它們如果想創建一個排好序的Vector令其只接收和生成String對象就會遇到麻煩因為addElement()和elementAt()都具有final屬性而且它們都是我們必須覆蓋的方法否則便無法實現只能接收和產生String對象
　　但在另一方面請考慮采用合成方法將一個對象置入一個新類的內部此時不是改寫上述代碼來達到這個目的而是在新類裡簡單地使用一個SortVector在這種情況下用於實現Compare接口的內部類就可以匿名地創建如下所示
　　
　　//: StrSortVectorjava
　　// Automatically sorted Vector that
　　// accepts and produces only Strings
　　package c;
　　import javautil*;
　　
　　public class StrSortVector {
　　　private SortVector v = new SortVector(
　　　　// Anonymous inner class:
　　　　new Compare() {
　　　　　public boolean
　　　　　lessThan(Object l Object r) {
　　　　　　return
　　　　　　　((String)l)toLowerCase(pareTo(
　　　　　　　((String)r)toLowerCase()) < ;
　　　　　}
　　　　　public boolean
　　　　　lessThanOrEqual(Object l Object r) {
　　　　　　return
　　　　　　　((String)l)toLowerCase(pareTo(
　　　　　　　((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的代碼，從而獲得希望的功能。tW.WIngwIT.COM然而，並不是來自SortVector和Vector的所有public方法都能在StrSortVector中出現。若按這種形式再生代碼，可在新類裡為包含類內的每一個方法都生成一個定義。當然，也可以在剛開始時只添加少數幾個，以後根據需要再添加更多的。新類的設計最終會穩定下來。
　　這種方法的好處在於它仍然只接納String對象，也只產生String對象。而且相應的檢查是在編譯期間進行的，而非在運行期。當然，只有addElement()和elementAt()才具備這一特性；elements()仍然會產生一個Enumeration（枚舉），它在編譯期的類型是未定的。當然，對Enumeration以及在StrSortVector中的類型檢查會照舊進行；如果真的有什麼錯誤，運行期間會簡單地產生一個違例。事實上，我們在編譯或運行期間能保
From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25414.html