您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C 語言核心排序算法精講：從桶排序到快速排序的完整遞進

編輯：C 語言入門

排序算法是程序設計的內功心法。本文以 C 語言為載體，按「認知負荷由低到高」順序，系統講解桶排序、插入排序、冒泡排序、快速排序四大經典算法，包含核心思想、代碼實現、優化技巧、時空複雜度分析及避坑指南，助你建立扎實的算法直覺。

算法全景對比

算法	平均時間	最壞時間	空間	穩定性	適用場景
桶排序	O(n+k)	O(n+k)	O(k)	穩定	數據範圍小、整數、非比較類
插入排序	O(n²)	O(n²)	O(1)	穩定	小規模、近乎有序、在線數據
冒泡排序	O(n²)	O(n²)	O(1)	穩定	教學、極小數據、檢測有序性
快速排序	O(n log n)	O(n²)	O(log n)	不穩定	通用大規模、內存敏感、庫函數標配

1. 桶排序：以空間換時間的極致

核心思想

適用於「已知數據範圍」的整數排序。申請大小為範圍的計數陣列（桶），遍歷輸入遞增對應桶，最後按順序輸出桶索引。

基礎版

#define MAXV 1000
void BucketSortBasic(int *a, int n) {
    int bucket[MAXV] = {0};
    for (int i = 0; i < n; ++i) bucket[a[i]]++;
    int idx = 0;
    for (int v = 0; v < MAXV; ++v)
        while (bucket[v]--) a[idx++] = v;
}

優化版：動態確定邊界


void BucketSortOptimized(int *a, int n) {
    if (n <= 1) return;
    int min = a[0], max = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }
    int range = max - min + 1;
    int *bucket = (int*)calloc(range, sizeof(int));
    for (int i = 0; i < n; ++i) bucket[a[i] - min]++;
    int idx = 0;
    for (int v = 0; v < range; ++v)
        while (bucket[v]--) a[idx++] = v + min;
    free(bucket);
}

負數處理

統一偏移：bucket[a[i] - min]++，輸出時 v + min。calloc 自動歸零，避免棧溢出。

局限性

數據範圍大時空間爆炸（如 32 位整數需 16GB 內存）
不適用浮點數、字符串、結構體
非原地排序，需額外輸出陣列或覆蓋原數組

2. 插入排序：構建有序區的匠心

核心思想

維護前綴有序區。從第二個元素開始，將當前元素插入已排序的前綴正確位置，類似整理撲克牌。

代碼實現


void InsertionSort(int *a, int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {  // 向右挪移大於 key 的元素
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;  // 插入空位
    }
}

優化點

二分查找插入位置：O(log i) 定位，但移動元素仍 O(i)，總體仍 O(n²)，適合比較操作昂貴場景
哨兵優化：a[0] 作哨兵，省去 j>=0 判斷
希爾排序：分組插入，間隔逐漸縮小至 1，平均 O(n^1.3)

優勢場景

小數組 (<50) 實際比快排更快（常數因子小）
近乎有序數組 O(n) 線性時間
在線排序：數據流式到達，隨到隨插
穩定排序需求

3. 冒泡排序：教科書級的「笨辦法」

核心思想

重複掃描數組，相鄰逆序對交換，大元素像氣泡一樣「浮」到右端。每輪確定一個最大值位置。

標準版


void BubbleSort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

優化版：提前終止 + 雙向冒泡 (雞尾酒排序)


void BubbleSortOptimized(int *a, int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        int last_swap = left;
        // 正向冒泡：最大值移到 right
        for (int j = left; j < right; ++j)
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                last_swap = j;
            }
        right = last_swap;  // 最後交換位置後已有序
        if (left >= right) break;
        // 反向冒泡：最小值移到 left
        last_swap = right;
        for (int j = right; j > left; --j)
            if (a[j - 1] > a[j]) {
                int tmp = a[j]; a[j] = a[j - 1]; a[j - 1] = tmp;
                last_swap = j;
            }
        left = last_swap;
    }
}

教學價值

雖實戰罕用，但完美展示「雙重循環邊界控制」、「交換邏輯」、「優化思維（記錄最後交換位置）」，是初學者理解迴圈不變量的最佳素材。

4. 快速排序：分治法的巔峰之作

核心思想

分治：選基準 → 分區（左小右大）→ 遞歸排左右子區。原地分區，空間僅遞歸棧 O(log n)。

單向掃描分區


int Partition(int *a, int low, int high) {
    int pivot = a[low];  // 選首元素為基準
    while (low < high) {
        while (low < high && a[high] >= pivot) --high;
        a[low] = a[high];  // 填坑
        while (low < high && a[low] <= pivot) ++low;
        a[high] = a[low];  // 填坑
    }
    a[low] = pivot;  // 基準歸位
    return low;
}

void QuickSort(int *a, int low, int high) {
    if (low < high) {
        int pivot = Partition(a, low, high);
        QuickSort(a, low, pivot - 1);
        QuickSort(a, pivot + 1, high);
    }
}

關鍵細節：為什麼必須先從右向左掃描？

因為首元素作基準並被保存，a[low] 位置空出成為第一個「坑」。若先從左掃描找到 >=pivot 填入 a[high]，會覆蓋未處理的數據。先從右找 <pivot 填入 a[low]，再從左找 >pivot 填入 a[high]，交替填坑，最終 low==high 坑位歸還基準值，保證左側 ≤ 基準 ≤ 右側。

工程級優化策略

優化	目的	實現
三數取中選基準	避免有序/逆序數組退化 O(n²)	取 `low, mid, high` 中位數，與 `low` 交換
小區間切換插入排序	減少遞歸開銷，利用插入排序小數組優勢	`if (high - low < 16) InsertionSort(a+low, high-low+1);`
尾遞歸消除	限制棧深度 `O(log n)`	遞歸處理較小分區，較大分區迴圈迭代
三向切分	大量重複鍵值時 `O(n)`	Dijkstra 荷蘭國旗算法：`<pivot \| =pivot \| >pivot`
隨機化基準	期望 `O(n log n)`，防惡意構造	`swap(a[low], a[rand()%(high-low+1)+low]);`

非遞歸實現（顯式棧）


void QuickSortIterative(int *a, int n) {
    struct Range { int low, high; };
    struct Range stack[64];  // log2(10^9) < 32
    int top = 0;
    stack[top++] = (struct Range){0, n-1};
    while (top) {
        struct Range r = stack[--top];
        if (r.low >= r.high) continue;
        int p = Partition(a, r.low, r.high);
        // 先壓入大分區，再壓入小分區，棧深度 O(log n)
        if (p - r.low > r.high - p) {
            stack[top++] = (struct Range){r.low, p-1};
            stack[top++] = (struct Range){p+1, r.high};
        } else {
            stack[top++] = (struct Range){p+1, r.high};
            stack[top++] = (struct Range){r.low, p-1};
        }
    }
}