經典排序演算法 C 語言實作全總覽：插入、歸並、堆積、快速、計數排序

前言

排序演算法是資料結構與演算法的基石。本文整理五大經典排序——插入排序、歸並排序、堆積排序、快速排序、計數排序——的 C 語言完整實作，並附上統一測試主程式，方便直接編譯驗證。所有程式碼均參考《演算法導論》經典版本，註解詳細，適合教學與快速查閱。

五大排序演算法實作細節

1. 插入排序 — O(n²)、穩定、原地

適合小規模或近乎有序資料。核心邏輯：將當前元素 key 插入已排序的左側子陣列中。

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

2. 歸並排序 — O(n log n)、穩定、需額外空間

分治法典範。遞迴將陣列對半分割至單元素，再合併兩個有序子陣列。使用哨兵值 0x7fffffff 簡化合併邏輯。

void merge(int *a, int s, int m, int e) {
    int n1 = m - s + 1, n2 = e - m;
    int *L = calloc(n1+1, sizeof(int));
    int *R = calloc(n2+1, sizeof(int));
    for (int i=0; i<n1; i++) L[i] = a[s+i];
    for (int j=0; j<n2; j++) R[j] = a[m+1+j];
    L[n1] = R[n2] = INT_MAX;           // 哨兵
    for (int i=s, x=0, y=0; i<=e; i++)
        a[i] = (L[x] <= R[y]) ? L[x++] : R[y++];
    free(L); free(R);
}
void sort_merge(int *a, int s, int e) {
    if (s < e) {
        int m = (s+e)/2;
        sort_merge(a, s, m);
        sort_merge(a, m+1, e);
        merge(a, s, m, e);
    }
}

3. 堆積排序 — O(n log n)、不穩定、原地

利用最大堆積性質。陣列下標從 1 開始，根節點為最大值。先建堆 build_max_heap，再重複交換堆頂與末尾元素並縮小堆大小。

void max_heapify(int *a, int i, int size) {
    int l = 2*i, r = 2*i+1, largest = i;
    if (l <= size && a[l] > a[largest]) largest = l;
    if (r <= size && a[r] > a[largest]) largest = r;
    if (largest != i) {
        swap(&a[i], &a[largest]);
        max_heapify(a, largest, size);
    }
}
void heap_sort(int *a, int n) {
    build_max_heap(a, n);
    for (int i=n; i>0; i--) {
        swap(&a[1], &a[i]);
        max_heapify(a, 1, i-1);
    }
}

4. 快速排序 — 平均 O(n log n)、不穩定、原地

單樞紐分割（Lomuto 分割）。partition 將小於樞紐的元素移至左側，最後將樞紐置於正確位置。

int partition(int *a, int s, int e) {
    int j = s-1;
    for (int i=s; i

void count_sort(int *a, int n, int *res) {
    int max = a[0];
    for (int i=1; i max) max = a[i];
    int *cnt = calloc(max+1, sizeof(int));
    for (int i=0; i=0; i--) res[--cnt[a[i]]] = a[i];
    free(cnt);
}

int main() {
    int a[20] = {9,10,8,11,7,12,6,13,5,14,4,15,3,16,2,18,20,1,19,17};
    int res[21];

    // 插入排序
    memcpy(res, a, sizeof(a));
    sort_insert(res, 20);
    print_arr(res, 20, "Insert Sort");

    // 歸並排序
    memcpy(res, a, sizeof(a));
    sort_merge(res, 0, 19);
    print_arr(res, 20, "Merge Sort");

    // 堆積排序（下標 1 起）
    for (int i=0; i<20; i++) res[i+1] = a[i];
    heap_sort(res, 20);
    print_arr(res+1, 20, "Heap Sort");

    // 快速排序
    memcpy(res, a, sizeof(a));
    quick_sort(res, 0, 19);
    print_arr(res, 20, "Quick Sort");

    // 計數排序（含重複值測試）
    a[3] = a[4] = 10;
    count_sort(a, 20, res);
    print_arr(res, 20, "Count Sort");
    return 0;
}