快速排序 C 語言實現：原地分區遞歸的經典演算法完整代碼與關鍵細節

演算法核心：分治法與原地分區

快速排序平均時間複雜度 O(N log N)，是實務中最高效的通用排序演算法之一。核心步驟：

1. 選取基準值（pivot）
2. 分區：將小於 pivot 的元素移到左側，大於的移到右側
3. 遞歸處理左右子陣列

完整 C 語言實現（霍爾分區方案）

#include <stdio.h>
#include <stdlib.h>

typedef int Elem;

typedef struct {
    Elem key;
    int data;
} Sqlist;

// 快速排序主函數
void quicksort(Sqlist R[], int low, int high) {
    if (low >= high) return;

    int i = low, j = high;
    Sqlist pivot = R[i]; // 選首元素為基準

    while (i != j) {
        // 從右向左找第一個小於 pivot.key 的元素
        while (i < j && pivot.key <= R[j].key) j--;
        if (i < j) R[i++] = R[j];

        // 從左向右找第一個大於 pivot.key 的元素
        while (i < j && pivot.key >= R[i].key) i++;
        if (i < j) R[j--] = R[i];
    }
    R[i] = pivot; // 基準歸位

    quicksort(R, low, i - 1);  // 遞歸左半部
    quicksort(R, i + 1, high); // 遞歸右半部
}

// 測試主程式
int main() {
    Sqlist arr[10];
    for (int i = 0; i < 10; ++i) {
        arr[i].key = 10 - i; // 逆序輸入
        arr[i].data = i;
    }

    quicksort(arr, 0, 9);

    for (int i = 0; i < 10; ++i)
        printf("key:%d  data:%d\n", arr[i].key, arr[i].data);
    return 0;
}

關鍵細節深度解析

1. 基準值選擇策略

• 固定首元素：代碼簡單，但有序/近乎有序資料退化為 O(N²)。
• 三數取中：取首、中、尾三者中位數作 pivot，大幅降低最壞情況概率。
• 隨機選取：期望複雜度 O(N log N)，工程上最推薦。

2. 分區邏輯的邊界條件

代碼中 while (i < j && pivot.key <= R[j].key) j--; 使用 <= 而非 <，確保與 pivot 相等的元素被移到右側，避免死循環。同理左側用 >=。這是霍爾分區法穩定性的關鍵。

3. 遞歸深度優化：尾遞歸消除

對較大的分區用遞歸，較小的用迭代（或直接尾遞歸優化），可將最壞棧深度從 O(N) 降至 O(log N)。

4. 小陣列切換插入排序

當 high - low < 10 時改用插入排序，減少遞歸開銷，工程級快排標配優化。

測試輸出驗證

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

輸入逆序，輸出有序，驗證演算法正確性。

總結

快速排序雖經典，但工程落地需關注：隨機化基準、三路分區（處理大量重複鍵）、尾遞歸優化、小陣列切換、非遞歸實現等。掌握霍爾分區邏輯與邊界條件，是從「會寫」到「寫好」的分水嶺。