快速排序算法圖解與 Java 實現：分治法核心邏輯深度剖析

算法核心思想

快速排序採用分治法：

1. 從數組選一個基準值（通常取首元素）
2. 一趟遍歷將數組分區：小於基準值的放左邊，大於的放右邊
3. 遞歸對左右子數組重複上述操作，直到子數組長度 ≤ 1

分區過程詳細步驟（雙指針法）

以數組 [21, 8, 2, 18, 0, 9, 27, 12, 5, 24] 為例，取首元素 21 為基準：

關鍵邏輯

1. 初始化：left=0（基準位置），right=9（末尾）
2. 從右向左找第一個 小於基準 的元素（記錄 right 索引）
3. 交換 left 和 right 位置元素，基準隨之移動到 right
4. 從左向右找第一個 大於基準 的元素（記錄 left 索引）
5. 交換 left 和 right 位置元素，基準移動到 left
6. 重複 2-5，直到 left == right，分區完成，基準歸位

完整排序演示過程

原數組： 21、8、2、18、0、9、27、12、5、24
第0次： 5、8、2、18、0、9、27、12、21、24    (基準21歸位)
第1次： 5、8、2、18、0、9、21、12、27、24    (右半區基準27歸位)
第2次： 5、8、2、18、0、9、12、21、27、24    (右半區基準12歸位)
第3次： 0、8、2、18、5、9、12、21、27、24    (左半區基準5歸位)
第4次： 0、5、2、18、8、9、12、21、27、24    (左半區基準8歸位)
第5次： 0、2、5、18、8、9、12、21、27、24    (左半區基準2歸位)
第6次： 0、2、5、12、8、9、18、21、27、24    (左半區基準18歸位)
第7次： 0、2、5、9、8、12、18、21、27、24    (左半區基準9歸位)
第8次： 0、2、5、8、9、12、18、21、27、24    (左半區基準8歸位)
第9次： 0、2、5、8、9、12、18、21、24、27    (右半區基準24歸位)

Java 代碼實現

public class QuickSort {
    private int time = 0; // 用於演示打印輪次
    
    /** 入口方法 */
    public void callQuickSort(int[] array) {
        printArray("原數組：", array);
        quickSort(array, 0, array.length - 1);
    }
    
    /** 遞歸排序主邏輯 */
    public void quickSort(int[] array, int left, int right) {
        if (left >= right) return; // 遞歸終止條件
        
        int index = qSort(array, left, right); // 分區，返回基準最終位置
        quickSort(array, left, index);         // 排序左半區
        quickSort(array, index + 1, right);    // 排序右半區
    }
    
    /** 單次分區核心邏輯 */
    private int qSort(int[] array, int left, int right) {
        int mid = left;           // 基準索引，初始為左端
        int temp;
        
        while (left < right) {
            if (mid != right) {   // 基準在左側，從右向左掃描
                if (array[mid] > array[right]) {
                    // 找到小於基準的元素，交換
                    temp = array[right];
                    array[right] = array[mid];
                    array[mid] = temp;
                    mid = right;  // 基準移動到 right 位置
                    printArray("第" + time++ + "次循環排序結果: ", array);
                } else {
                    right--;      // 繼續向左掃描
                }
            } else {              // 基準在右側，從左向右掃描
                if (array[left] > array[mid]) {
                    // 找到大於基準的元素，交換
                    temp = array[left];
                    array[left] = array[mid];
                    array[mid] = temp;
                    mid = left;   // 基準移動到 left 位置
                    printArray("第" + time++ + "次循環排序結果: ", array);
                } else {
                    left++;       // 繼續向右掃描
                }
            }
        }
        return mid; // 返回基準最終位置
    }
    
    private void printArray(String prefix, int[] array) {
        System.out.print(prefix);
        for (int n : array) System.out.print(n + "、");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] a = {21, 8, 2, 18, 0, 9, 27, 12, 5, 24};
        new QuickSort().callQuickSort(a);
    }
}

算法複雜度分析

優化方向

• 三數取中法：取首、中、尾三者中位數作基準，避免最壞情況
• 隨機基準：隨機選擇基準，期望複雜度 O(n log n)
• 小數組插入排序：長度 < 10 時改用插入排序
• 尾遞歸優化：優化較大分區的遞歸調用
• 三向切分：處理大量重複鍵值（荷蘭國旗問題）

遞歸理解關鍵

不熟練遞歸的同學建議先閱讀：遞歸核心原理圖解

核心思想：大問題分解為同結構的小問題，直到基線條件終止。