C語言快速排序完整實作：結構體排序、遞迴分治與邊界優化

編輯：關於C語言

C語言快速排序完整實作：結構體排序、遞迴分治與邊界優化

快速排序是平均 O(n log n)、原地排序的經典演算法。本文提供針對結構體陣列的完整實作，包含單趟劃分、遞迴排序、主程式測試，並分析樞紐選擇策略、尾遞迴優化、三向切分等進階改良方向。

完整可編譯代碼

#include <stdio.h>

typedef struct Node {
    int key;
} Node;

typedef Node DataType;

// 前向宣告
int QuickPassSort(DataType arr[], int low, int high);
void QuickSort(DataType arr[], int low, int high);

int main() {
    int n, i;
    DataType array[20];

    printf("輸入陣列長度 (<20): ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("輸入第 %d 個資料: ", i + 1);
        scanf("%d", &array[i].key);
    }

    printf("\n原始陣列: ");
    for (i = 0; i < n; i++) printf("%4d", array[i].key);

    QuickSort(array, 0, n - 1);

    printf("\n排序後陣列: ");
    for (i = 0; i < n; i++) printf("%4d", array[i].key);
    printf("\n");
    return 0;
}

// 快速排序主遞迴函數
void QuickSort(DataType arr[], int low, int high) {
    if (low < high) {
        int pivotIdx = QuickPassSort(arr, low, high);
        QuickSort(arr, low, pivotIdx - 1);   // 排序左半部
        QuickSort(arr, pivotIdx + 1, high);  // 排序右半部
    }
}

// 單趟劃分：Hoare 分割法變體
int QuickPassSort(DataType arr[], int low, int high) {
    DataType pivot = arr[low];  // 選第一個元素為樞紐
    int i = low, j = high;

    while (i < j) {
        // 從右向左找第一個小於樞紐的元素
        while (i < j && pivot.key <= arr[j].key) j--;
        if (i < j) {
            arr[i] = arr[j];  // 移到左邊
            i++;
        }

        // 從左向右找第一個大於樞紐的元素
        while (i < j && arr[i].key <= pivot.key) i++;
        if (i < j) {
            arr[j] = arr[i];  // 移到右邊
            j--;
        }
    }

    arr[i] = pivot;  // 樞紐歸位
    return i;        // 回傳樞紐最終位置
}

核心邏輯圖解：Hoare 分割過程

初始: [pivot, ..., ..., ..., ...]
       i                     j

步驟 1: j 左移找 < pivot
步驟 2: 將 arr[j] 複製到 arr[i], i++
步驟 3: i 右移找 > pivot
步驟 4: 將 arr[i] 複製到 arr[j], j--
重複 1-4 直到 i == j
最終: 將 pivot 放入 arr[i]
返回 i 作為分割點

關鍵優化方向

優化點	問題	解決方案	效果
樞紐選擇	固定選首/尾元素，有序陣列退化 O(n²)	三數取中、隨機樞紐、九數取中	期望 O(n log n)
小陣列切換	遞迴開銷大於排序獲益	閾值 < 10-20 切換插入排序	減少 20%+ 時間
尾遞迴消除	遞迴棧深度 O(n) 風險	迴圈處理較大分區，遞迴處理較小	棧深度 O(log n)
三向切分	大量重複鍵值導致不平衡	Dijkstra 荷蘭國旗問題：<pivot, =pivot, >pivot	重複鍵值 O(n)
內省排序	惡意輸入攻擊	深度超過 2 log n 切換堆排序	最壞 O(n log n)

三向切分實作（處理重複鍵值）

void QuickSort3Way(DataType arr[], int low, int high) {
    if (low >= high) return;

    int lt = low, gt = high;
    DataType pivot = arr[low];
    int i = low + 1;

    while (i <= gt) {
        if (arr[i].key < pivot.key) {
            swap(&arr[lt++], &arr[i++]);
        } else if (arr[i].key > pivot.key) {
            swap(&arr[i], &arr[gt--]);
        } else {
            i++;
        }
    }
    // 現在 [low..lt-1] < pivot, [lt..gt] == pivot, [gt+1..high] > pivot
    QuickSort3Way(arr, low, lt - 1);
    QuickSort3Way(arr, gt + 1, high);
}

尾遞迴優化版

void QuickSortTailRec(DataType arr[], int low, int high) {
    while (low < high) {
        int pivotIdx = QuickPassSort(arr, low, high);
        // 遞迴處理較小分區，迴圈處理較大分區
        if (pivotIdx - low < high - pivotIdx) {
            QuickSortTailRec(arr, low, pivotIdx - 1);
            low = pivotIdx + 1;
        } else {
            QuickSortTailRec(arr, pivotIdx + 1, high);
            high = pivotIdx - 1;
        }
    }
}

測試驗證建議

隨機陣列：驗證平均效能。
已排序/逆序陣列：驗證樞紐策略是否退化。
全相同元素：驗證三向切分必要性。
大量重複鍵值：如 100 萬元素只有 10 個不同值。
邊界大小：0, 1, 2, INT_MAX 附近。

與標準庫 qsort 比較

// qsort 使用示範
int compare(const void *a, const void *b) {
    return ((DataType*)a)->key - ((DataType*)b)->key;
}
qsort(array, n, sizeof(DataType), compare);