經典排序算法 C 語言實現總結：插入/選擇/交換/歸並四大類完整代碼

基礎概念速覽

• 穩定性：相等鍵值相對順序保持
• 內/外排序：全內存 vs 內外存交換
• 時間/空間複雜度：比較移動次數與輔助空間

插入排序類

1. 直接插入排序（穩定，O(n²)）

void Dir_Insert(int *x, int N) {
    for (int i = 1; i < N; i++) {
        int tmp = x[i], j = i-1;
        while (j >= 0 && x[j] > tmp) {
            x[j+1] = x[j];
            j--;
        }
        x[j+1] = tmp;
    }
}

2. 希爾排序（不穩定，O(n^1.3)）

void shell_sort(int *x, int N) {
    for (int h = N/2; h > 0; h /= 2)
        for (int j = h; j < N; j++) {
            int t = x[j], k;
            for (k = j-h; k >= 0 && t < x[k]; k -= h)
                x[k+h] = x[k];
            x[k+h] = t;
        }
}

選擇排序類

1. 直接選擇排序（不穩定，O(n²)）

void select_sort(int *x, int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++)
            if (x[j] < x[min]) min = j;
        if (min != i) swap(x[i], x[min]);
    }
}

2. 堆排序（不穩定，O(n log n)）

利用大根堆/小根堆特性，建堆 O(n)，每次取頂調整 O(log n)。代碼較長，核心：heapify + build_heap + 循環提取。

交換排序類

1. 冒泡排序（穩定，O(n²)）

void BubbleSort(int *x, int N) {
    for (int i = N-1; i > 0; i--)
        for (int j = 0; j < i; j++)
            if (x[j] > x[j+1]) swap(x[j], x[j+1]);
}

2. 快速排序（不穩定，平均 O(n log n)）

void quick_sort(int *x, int low, int high) {
    if (low < high) {
        int i = low, j = high, t = x[low];
        while (i < j) {
            while (i < j && x[j] > t) j--;
            if (i < j) x[i++] = x[j];
            while (i < j && x[i] <= t) i++;
            if (i < j) x[j--] = x[i];
        }
        x[i] = t;
        quick_sort(x, low, i-1);
        quick_sort(x, i+1, high);
    }
}

歸並排序（穩定，O(n log n)）

分治策略：遞歸分解至單元素，歸並合併有序子序列。需 O(n) 輔助空間，適合鏈表與外排序。

算法選型決策表

核心心法

快速排序是隨機數據下最快的比較排序；堆排序保證最壞 O(n log n) 且省空間；歸並排序提供穩定保證。工程中常混合策略：小區間插入、大區間快排、歸並用於外部/鏈表。

本文代碼均為 C 風格指針操作，易移植至嵌入式環境。