Java 排序演算法實作：回呼模式與泛型排序向量

問題：Java 1.0/1.1 缺乏內建排序

早期 Java 標準庫無排序功能。需自行實作通用排序程式碼，核心挑戰：如何根據物件實際型別比較大小？

解決方案：回呼模式

將不變的排序演算法與會變的比較邏輯分離：

interface Compare {
    boolean lessThan(Object lhs, Object rhs);
    boolean lessThanOrEqual(Object lhs, Object rhs);
}

• 排序程式碼「回呼」 Compare 方法；
• 不同物件實作不同 Compare，傳入同一排序類別；
• 達成「將變化的東西與不變的東西分隔開」的設計目標。

泛型排序向量：SortVector

public class SortVector extends Vector {
    private Compare compare;
    public SortVector(Compare comp) { compare = comp; }
    public void sort() { quickSort(0, size()-1); }
    // 快速排序實作中呼叫 compare.lessThan(...)
}

使用範例：字串不分大小寫排序

class StringCompare implements Compare {
    public boolean lessThan(Object l, Object r) {
        return ((String)l).toLowerCase().compareTo(((String)r).toLowerCase()) < 0;
    }
    // lessThanOrEqual 類似
}

SortVector sv = new SortVector(new StringCompare());
sv.addElement("d"); sv.addElement("A"); ... sv.sort();

繼承 vs 組合：擴充性的代價

• 繼承：SortVector extends Vector，但 Vector 許多方法是 final，無法覆寫限制型別（如只接受 String）；
• 組合：StrSortVector 內含 SortVector，對外只暴露 String 方法，編譯期型別安全：

public class StrSortVector {
    private SortVector v = new SortVector(new Compare() { ... }); // 匿名內部類別
    public void addElement(String s) { v.addElement(s); sorted=false; }
    public String elementAt(int i) { if(!sorted) {v.sort(); sorted=true;} return (String)v.elementAt(i); }
}

懶惰求值優化

sorted 標記：只有真正需要讀取時才排序，避免每次 add 都排序，大幅提升批次插入效能。

參數化型別展望

Java 當時尚無泛型（JDK 5 引入），組合模式下 elements() 回傳 Enumeration 型別不確定。泛型化後可徹底解決型別安全問題。

總結

回呼模式實現演算法與比較邏輯解耦；組合優於繼承提供型別安全擴充；懶惰求值優化效能。這些模式在現代 Java（Collections.sort、Comparator、泛型、Lambda）中皆有更完善實現。