快速排序算法C語言完整實現與核心邏輯深度解析

快速排序：從原理到高性能C語言實現

快速排序是經典的分治算法，平均時間復雜度O(n log n)，原地排序，空間復雜度O(log n)（遞歸棧）。本文提供標準C實現，並深度剖析分區邏輯、遞歸終止條件、以及工程化優化方向。

核心代碼實現

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

/* 
 * 單向掃描分區法（Lomuto partition scheme的變體）
 * 以首元素為基準，將數組劃分為「≤基準」和「>基準」兩區
 * 返回基準元素最終位置索引
 */
int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 基準值
    int left = low;
    int right = high;
    
    while (left < right) {
        /* 從右向左找第一個 < pivot 的元素 */
        while (left < right && arr[right] >= pivot) 
            right--;
        arr[left] = arr[right];  // 將較小元素移到左側空位
        
        /* 從左向右找第一個 > pivot 的元素 */
        while (left < right && arr[left] <= pivot) 
            left++;
        arr[right] = arr[left];  // 將較大元素移到右側空位
    }
    
    arr[left] = pivot;  // 基準歸位
    return left;        // 返回分區點
}

/* 遞歸快速排序入口 */
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pos = partition(arr, low, high);
        quick_sort(arr, low, pos - 1);   // 排序左分區
        quick_sort(arr, pos + 1, high);  // 排序右分區
    }
}

/* 測試主程序 */
int main(void) {
    int data[] = {32, 33, 21, 14, 36, 7, 6, 4, 2, 11};
    int n = sizeof(data) / sizeof(data[0]);
    
    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%d ", data[i]);
    printf("\n");
    
    quick_sort(data, 0, n - 1);
    
    printf("排序後: ");
    for (int i = 0; i < n; i++) printf("%d ", data[i]);
    printf("\n");
    return 0;
}

分區邏輯圖解

以數組[32, 33, 21, 14, 36, 7, 6, 4, 2, 11]為例，首輪分區過程：

1. 基準pivot=32，left=0，right=9
2. 右掃描：11<32停在索引9，arr[0]=11
3. 左掃描：33>32停在索引1，arr[9]=33
4. 右掃描：2<32停在索引8，arr[1]=2
5. 左掃描：36>32停在索引4，arr[8]=36
6. ...繼續直到left==right==4
7. 最終arr[4]=32，左側全≤32，右側全>32

關鍵技術細節

1. 基準值選擇策略的影響

• 固定首元素：已排序/逆序數組退化為O(n²)
• 三數取中法：median(arr[low], arr[mid], arr[high])，大幅降低最壞情況概率
• 隨機選取：期望時間複雜度穩定O(n log n)

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

void quick_sort_opt(int arr[], int low, int high) {
    while (low < high) {
        int pos = partition(arr, low, high);
        /* 遞歸處理較小分區，迭代處理較大分區 */
        if (pos - low < high - pos) {
            quick_sort_opt(arr, low, pos - 1);
            low = pos + 1;  // 尾遞歸轉迭代
        } else {
            quick_sort_opt(arr, pos + 1, high);
            high = pos - 1;
        }
    }
}

保證最大遞歸深度O(log n)，避免棧溢出。

3. 小數組切換插入排序

當high - low < 16時，插入排序因常數因子小而更快：

if (high - low < 16) {
    insertion_sort(arr, low, high);
    return;
}

4. 三向切分應對重複鍵值

荷蘭國旗問題思路，將數組分為<pivot、=pivot、>pivot三區，大量重複元素時從O(n²)優化到O(n)。

工程化建議

測試驗證

/* 自測用例建議 */
int test_cases[][10] = {
    {5,4,3,2,1},           // 逆序
    {1,2,3,4,5},           // 正序
    {3,3,3,3,3},           // 全相同
    {1},                   // 單元素
    {},                    // 空數組
    {9,1,8,2,7,3,6,4,5,0}  // 亂序
};

快速排序雖然代碼簡短，但「魔鬼在細節」：分區邏輯的邊界條件、基準選擇策略、遞歸深度控制、小數組優化，每一項都直接影響實際性能與穩定性。理解其核心機制，才能在面對具體場景時做出正確的工程選型與調優。