快速排序：從基礎分區到三向切分的完整演進

編輯：關於C語言

快速排序是實踐中最快的通用排序算法，平均 O(n log n)、原地排序、緩存友好。本文從經典 Hoare 分區演進到三向切分，解決重複鍵值性能退化問題。

核心思想：分治 + 分區

選擇基準元素
分區：將數組重排為 [< pivot] [= pivot] [> pivot]
遞歸排序左右子數組

分區方案演進

1. Lomuto 分區（教科書經典）

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 選末尾為基準
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return i + 1;
}

缺點：重複元素多時交換次數多，退化為 O(n²)。

2. Hoare 分區（原版，更高效）

int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 選首元素
    int i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

優點：交換次數少約 1/3，指針交錯停止。遞歸邊界為 [low, p] 和 [p+1, high]。

3. 三向切分（荷蘭國旗問題，處理重複鍵）

void quicksort_3way(int arr[], int low, int high) {
    if (low >= high) return;
    
    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low;
    
    while (i <= gt) {
        if (arr[i] < pivot) swap(&arr[lt++], &arr[i++]);
        else if (arr[i] > pivot) swap(&arr[i], &arr[gt--]);
        else i++;
    }
    
    quicksort_3way(arr, low, lt-1);
    quicksort_3way(arr, gt+1, high);
}

將數組分為 < pivot、= pivot、> pivot 三段，重複元素不再遞歸處理，大量重複鍵值時接近 O(n)。

基準選擇策略

策略	適用場景	缺點
固定首/尾	教學、隨機數據	有序/逆序數據退化
隨機選擇	通用、防惡意構造	需隨機數生成開銷
三數取中	工程實踐首選	中位數近似，穩健
九數取中	大規模數據	更精確，開銷稍大

工程優化清單

小數組切換插入排序：n < 15 時插入排序更快
尾遞歸消除：遞歸處理較小分區，迭代處理較大分區，棧深度 O(log n)
三向切分：含重複鍵值數據必備
隨機化打亂：排序前 shuffle 消除輸入分布依賴

完整優化版（C 實現）

#include <stdlib.h>
#include <time.h>

#define INSERTION_THRESHOLD 15

void insertion_sort(int arr[], int low, int high) {
    for (int i = low+1; i <= high; i++) {
        int key = arr[i], j = i-1;
        while (j >= low && arr[j] > key) arr[j+1] = arr[j--];
        arr[j+1] = key;
    }
}

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void quicksort(int arr[], int low, int high) {
    while (high - low > INSERTION_THRESHOLD) {
        // 三數取中
        int mid = low + (high - low) / 2;
        if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
        if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
        if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
        swap(&arr[mid], &arr[low]);  // 基準移到首位
        
        // 三向切分
        int pivot = arr[low];
        int lt = low, gt = high, i = low + 1;
        while (i <= gt) {
            if (arr[i] < pivot) swap(&arr[lt++], &arr[i++]);
            else if (arr[i] > pivot) swap(&arr[i], &arr[gt--]);
            else i++;
        }
        
        // 尾遞歸優化：遞歸較小部分
        if (lt - low < high - gt) {
            quicksort(arr, low, lt-1);
            low = gt + 1;
        } else {
            quicksort(arr, gt+1, high);
            high = lt - 1;
        }
    }
    insertion_sort(arr, low, high);
}

void quick_sort(int arr[], int n) {
    srand(time(NULL));
    // 可選：隨機打亂
    for (int i = n-1; i > 0; i--) {
        int j = rand() % (i+1);
        swap(&arr[i], &arr[j]);
    }
    quicksort(arr, 0, n-1);
}