快速排序極簡 C 實現：單邊掃描法 + 哨兵優化

核心代碼（含註釋）

/**
 * 快速排序：單邊掃描 + 哨兵
 * @param r  待排序陣列（長度 ≤ 1000）
 * @param s  起始索引（0-based）
 * @param e  結束索引（n-1）
 */
void quicksort(int r[1001], int s, int e) {
    if (s >= e) return;                 // 遞歸出口

    int pivot = r[s];                   // 哨兵：首元素
    int f = s + 1;                      // 前向指標
    int b = e;                          // 後向指標
    int tmp;

    while (f <= b) {
        while (f <= b && r[f] <= pivot) ++f;  // 找 > pivot
        while (f <= b && r[b] >= pivot) --b;  // 找 < pivot
        if (f < b) {                          // 交換雙邊錯位元素
            tmp = r[f]; r[f] = r[b]; r[b] = tmp;
            ++f; --b;
        }
    }

    // 將哨兵插入正確位置（b 指向最後一個 ≤ pivot 的元素）
    r[s] = r[b];
    r[b] = pivot;

    quicksort(r, s, b - 1);   // 左半部
    quicksort(r, b + 1, e);   // 右半部
}

關鍵點解析

1. 哨兵選首元素：簡單但最壞情況（有序陣列）退化 O(n²)。工程上常用「三數取中」或隨機化選樞軸。
2. r[f] <= pivot 與 r[b] >= pivot：包含等號，確保相等元素不會被無謂交換，穩定性雖無法保證但減少交換次數。
3. 重複鍵值處理：若全為相同值，f 會直接跑到 b+1，b 停在 s，分區點 b == s，左半部為空，右半部 n-1，仍退化。工程可改用「三向切分」（Dutch National Flag）。
4. 紙上模擬 + 調試器：作者建議畫圖配合單步調試，理解指標交會過程。

測試主程式

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

int main() {
    int n = 20, a[1001];
    srand(time(0));
    for (int i = 0; i < n; ++i) a[i] = rand() % 100;

    printf("Before: ");
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    putchar('\n');

    quicksort(a, 0, n - 1);

    printf("After:  ");
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    putchar('\n');
    return 0;
}

複雜度與改進方向

工程級改進：隨機化樞軸、三向切分、小區間改插入排序、尾遞歸消除、迭代版避免棧溢出。