Java 泛型實現通用數組排序與搜索：從 Object 到 Comparable 再到有界類型參數

演進歷程：三代通用算法 API 設計

第一代：Object 引用 + 強制轉型（JDK 1.0-1.4）

// 線性查找
public static int seqSearch(Object[] arr, int first, int last, Object target) {
    for (int i = first; i < last; i++)
        if (arr[i].equals(target)) return i;
    return -1;
}

// 選擇排序 - 警告：unchecked cast，運行時才拋 ClassCastException
@SuppressWarnings("unchecked")
public static void selectionSort(Object[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++)
            if (((Comparable<Object>) arr[minIdx]).compareTo((Comparable<Object>) arr[j]) > 0)
                minIdx = j;
        swap(arr, i, minIdx);
    }
}

缺陷： 編譯期無法檢查元素是否實現 Comparable，類型安全完全依賴運行時，違反「失敗快」原則。

第二代：泛型 + 有界類型參數（JDK 5+，標準庫做法）

/**
 * 通用選擇排序
 * @param  元素類型，必須實現 Comparable（支持父類比較）
 * @param arr 待排序數組（原地修改）
 */
public static <T extends Comparable<? super T>> void selectionSort(T[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++)
            if (arr[j].compareTo(arr[minIdx]) < 0)  // 編譯期保證類型安全
                minIdx = j;
        swap(arr, minIdx, i);
    }
}

private static <T> void swap(T[] arr, int i, int j) {
    T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}

類型參數解讀

• T extends Comparable<? super T>：
• Comparable<T> 要求 T 能與 自身 比較。
• Comparable<? super T> 放寬為 自身或父類 實現比較即可（如 Integer implements Comparable<Integer>，LocalDate implements Comparable<ChronoLocalDate>）。
• 這正是 java.util.Arrays.sort(T[]) 的簽名設計。

第三代：Comparator 策略模式（最大靈活性）

public static <T> void sort(T[] arr, Comparator<? super T> cmp) {
    // 可插入任意比較邏輯：倒序、多字段、忽略大小寫...
    Arrays.sort(arr, cmp);
}

// 使用示例
String[] names = {"Bob", "alice", "Charlie"};
sort(names, String.CASE_INSENSITIVE_ORDER); // 忽略大小寫排序
sort(names, Comparator.comparing(String::length).reversed()); // 長度降序

通用搜索：二分查找前提是有序

public static <T extends Comparable<? super T>> int binarySearch(T[] arr, T key) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int cmp = arr[mid].compareTo(key);
        if (cmp < 0) low = mid + 1;
        else if (cmp > 0) high = mid - 1;
        else return mid; // 找到
    }
    return -(low + 1); // 未找到，返回插入點編碼
}

實戰：多字段排序的 Comparator 鏈

record Employee(String name, int age, double salary) {}

Employee[] emps = {
    new Employee("張三", 30, 8000),
    new Employee("李四", 25, 12000),
    new Employee("王五", 30, 9000)
};

// 年齡升序，年齡相同則薪資降序
Comparator cmp = Comparator
    .comparingInt(Employee::age)
    .thenComparingDouble(Employee::salary).reversed();

Arrays.sort(emps, cmp);
// 結果：李四(25,12000) → 王五(30,9000) → 張三(30,8000)

性能與內存考量

常見陷阱與避坑指南

• 泛型數組創建： new T[10] 編譯錯誤，需 (T[]) new Object[10] 或 Array.newInstance(clazz, 10)。
• 類型擦除導致的警告： @SuppressWarnings("unchecked") 僅在確信安全時使用（如框架內部）。
• Comparable 一致性： compareTo 必須與 equals 一致，否則 TreeSet/TreeMap 會違反集合契約。
• null 元素： Comparable 不處理 null，需自定義 Comparator.nullsFirst() 或預處理過濾。

總結

Java 泛型將「通用算法」從 運行時類型檢查 升級為 編譯期類型證明。核心設計模式是 有界類型參數 <T extends Comparable<? super T>> 配合 Comparator 策略注入。這正是 java.util.Arrays、Collections、Stream API 的基石設計。掌握此模式，即可編寫類型安全、可復用、高性能的通用數據結構與算法庫。