快速排序算法 C 語言完整實現與解析

快速排序算法 C 語言完整實現與解析

快速排序是經典的分治算法，平均時間複雜度 O(n log n)，本文提供完整可運行的 C 實現代碼，並解析核心分區邏輯。

數據結構定義

#define Elem int

typedef struct sqlist {
    Elem key;   // 排序關鍵字
    int data;   // 附帶數據
} sqlist;

核心遞歸函數

void quicksort(sqlist R[], int low, int high) {
    int i = low, j = high;
    sqlist temp;

    if (low < high) {
        temp = R[i];           // 基準值
        while (i != j) {
            // 從右向左找第一個小於基準的元素
            while (i < j && temp.key < R[j].key) j--;
            if (i < j) R[i++] = R[j];  // 移至左側，i 後移

            // 從左向右找第一個大於基準的元素
            while (i < j && temp.key > R[i].key) i++;
            if (i < j) R[j--] = R[i];  // 移至右側，j 前移
        }
        R[i] = temp;           // 基準值歸位
        quicksort(R, low, i - 1);   // 遞歸排序左半部
        quicksort(R, i + 1, high);  // 遞歸排序右半部
    }
}

主函數測試

int main() {
    sqlist dataSort[10];
    // 初始化逆序數據
    for (int i = 0; i < 10; i++) {
        dataSort[i].key = 10 - i;
        dataSort[i].data = i;
    }

    quicksort(dataSort, 0, 9);

    // 輸出結果
    for (int i = 0; i < 10; i++) {
        printf("key:%d  data:%d\n", dataSort[i].key, dataSort[i].data);
    }
    return 0;
}

執行結果

key:1  data:9
key:2  data:8
key:3  data:7
key:4  data:6
key:5  data:5
key:6  data:4
key:7  data:3
key:8  data:2
key:9  data:1
key:10 data:0

算法關鍵點解析

優化方向

1. 基準選擇：三數取中（首、中、尾）避免有序數組退化到 O(n²)
2. 小區間切換：元素數 < 10 時改用插入排序
3. 尾遞歸優化：對較大分區遞歸，較小分區迭代，減少棧深度
4. 三向切分：處理大量重複鍵值（Dutch National Flag 算法）

複雜度總結

• 平均：O(n log n)
• 最差：O(n²)（已有序數組 + 首元素基準）
• 空間：O(log n) 遞歸棧（尾遞歸優化後）
• 穩定性：不穩定

快速排序是工程實踐中最常用的內部排序算法，理解其分區邏輯與優化技巧是程序員必備基本功。