Java 泛型實現通用快速排序：支援任意 Comparable 類型與基本類型

快速排序核心邏輯回顧

1. 選 基準值 (pivot，通常取首/中/隨機元素)。
2. 分區：小於 pivot 左邊，大於 pivot 右邊。
3. 遞歸排序左右子陣列，直到長度 ≤ 1。

泛型版核心實現

public class GenericQuickSort {
    
    // 入口：支援任意實現 Comparable 的類型
    public static > void sort(T[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static > void quickSort(T[] arr, int low, int high) {
        if (low >= high) return;
        
        int pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, high);
    }
    
    // 單向掃描分區 (Lomuto 方案，易理解)
    private static > int partition(T[] arr, int low, int high) {
        T pivot = arr[high]; // 選最後一個為基準
        int i = low - 1;     // 小於區域邊界
        
        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) { // <= 保證穩定性傾向
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high); // 基準歸位
        return i + 1;
    }
    
    private static  void swap(T[] arr, int i, int j) {
        T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

基本類型支援：重載 + 裝箱/拆箱

public class QuickSortUtils {
    
    // 物件陣列通用入口
    public static > void sort(T[] arr) {
        GenericQuickSort.sort(arr);
    }
    
    // List 版本
    public static > void sort(List list) {
        if (list == null || list.size() <= 1) return;
        @SuppressWarnings("unchecked")
        T[] arr = (T[]) list.toArray(); // 可能類型擦除警告，實際安全
        sort(arr);
        // 寫回 List
        for (int i = 0; i < arr.length; i++) list.set(i, arr[i]);
    }
    
    // 基本類型重載 (避免裝箱開銷的話需複製代碼，這裡演示裝箱簡易版)
    public static void sort(int[] arr) {
        Integer[] boxed = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) boxed[i] = arr[i];
        sort(boxed);
        for (int i = 0; i < arr.length; i++) arr[i] = boxed[i];
    }
    
    public static void sort(double[] arr) {
        Double[] boxed = new Double[arr.length];
        for (int i = 0; i < arr.length; i++) boxed[i] = arr[i];
        sort(boxed);
        for (int i = 0; i < arr.length; i++) arr[i] = boxed[i];
    }
    
    // long、float、short、byte、char 同理...
}

測試驗證

public class QuickSortTest {
    public static void main(String[] args) {
        // 1. 基本類型
        int[] nums = {64, 34, 25, 12, 22, 11, 90};
        QuickSortUtils.sort(nums);
        System.out.println("int[]: " + Arrays.toString(nums)); // [11, 12, 22, 25, 34, 64, 90]
        
        // 2. 物件類型 (String 實現 Comparable)
        String[] words = {"delta", "alpha", "epsilon", "beta", "gamma"};
        QuickSortUtils.sort(words);
        System.out.println("String[]: " + Arrays.toString(words)); // [alpha, beta, delta, epsilon, gamma]
        
        // 3. 自定義類型
        List students = Arrays.asList(
            new Student("張三", 85), new Student("李四", 92), new Student("王五", 78)
        );
        QuickSortUtils.sort(students); // 按分數升序 (Student 實現 Comparable)
        System.out.println("Students: " + students);
    }
}

class Student implements Comparable {
    String name; int score;
    Student(String n, int s) { name = n; score = s; }
    public int compareTo(Student o) { return Integer.compare(this.score, o.score); }
    public String toString() { return name + "(" + score + ")"; }
}

關鍵泛型設計解析

優化方向 (生產級)

1. 三數取中法：取首、中、末三者中位數作 pivot，避免有序數組退化 O(n²)。
2. 小數組切換插入排序：長度 < 15 用插入排序，減少遞歸開銷。
3. 三向切分：大量重複鍵時，分為 <、=、> 三區，避免重複元素遞歸。
4. 尾遞歸消除 / 顯式棧：避免棧溢出，手動管理棧模擬遞歸。
5. 隨機化 pivot：swap(arr, high, random.nextInt(high-low+1)+low)，期望 O(n log n)。

JDK 內建排序對比

// 實際開發直接用：
Arrays.sort(arr);              // 基本類型：Dual-Pivot Quicksort (Yaroslavskiy 2009)
Arrays.sort(objArr);           // 物件：TimSort (Python 移植)，穩定、適應性強
Collections.sort(list);        // 委託 Arrays.sort

結論：教學/面試手寫快排；生產代碼直接用 JDK 內建，經過極致優化、穩定、支援並行 (Arrays.parallelSort)。

1. 上一篇文章： Struts2 S2-032 (CVE-2016-3081) 遠程代碼執行漏洞深度剖析與防禦
2. 下一篇文章： 迭代器模式 Java 實現：統一遍歷介面、封裝聚合內部結構

Java 相關知識

Java 6 WebService 入門：零依賴快速構建 SOAP 服務

背景 傳統開發依賴 CXF、Axis2、XFire 等框架，

RAP 與 RCP 架構差異深度解析：從 Eclipse 插件到 Web 應用

Eclipse 生態系中的 RAP (Rich Ajax P

Axis2 模組開發全攻略：從 Module/Handler 到 .mar 部署

Axis2 透過模組擴展功能，核心需實作兩個介面：Modul

JVM 類別卸載與類別更新機制深度解析

規範定義：何時會卸載類別？ JVM Spec 僅兩句話：