C 語言經典排序算法全解析：選擇、插入、冒泡、希爾、快速排序

編輯：關於C語言

基礎概念

穩定性：相等元素排序後相對順序不變為穩定。
內排序：全過程在內存完成；外排序：需借助外存。
時間/空間複雜度：衡量算法優劣核心指標。

1. 選擇排序

思想：每輪從無序區選最小元素，與無序區首位交換。

特性：不穩定，O(n²)，交換次數少 (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) {
            int t = x[i]; x[i] = x[min]; x[min] = t;
        }
    }
}

2. 直接插入排序

思想：將無序區首元素插入有序區適當位置，類似整理撲克牌。

特性：穩定，O(n²)，近乎有序時極快 (O(n))。


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

3. 冒泡排序 (改進版)

思想：相鄰比較，大者後沉，小者前冒。記錄最後交換位置縮小掃描範圍。

特性：穩定，O(n²)，有序時可提前結束。


void bubble_sort(int *x, int n) {
    int k, h = n-1;
    while (h > 0) {
        k = 0;
        for (int j = 0; j < h; j++)
            if (x[j] > x[j+1]) {
                int t = x[j]; x[j] = x[j+1]; x[j+1] = t;
                k = j;
            }
        h = k;
    }
}

4. 希爾排序

思想：按增量分組插入排序，增量逐漸減至 1。打破「只能相鄰移動」限制，大幅減少移動次數。

特性：不穩定，增量序列影響性能 (常用 n/2, n/4... 或 Sedgewick 序列)，平均 O(n¹·³)~O(n log²n)。


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

5. 快速排序 (遞歸版)

思想：分治法。選基準，一趟掃描將數組分為「小於基準」和「大於基準」兩部分，遞歸處理。

特性：不穩定，平均 O(n log n)，最壞 O(n²) (已有序時)。工程上常用「三數取中」選基準 + 小區間改插入排序 + 尾遞歸優化。


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

性能對比與選型建議

算法	平均時間	最壞時間	空間	穩定	適用場景
選擇	O(n²)	O(n²)	O(1)	否	數據量極小、交換代價極大
插入	O(n²)	O(n²)	O(1)	是	近乎有序、小數據量、在線排序
冒泡	O(n²)	O(n²)	O(1)	是	教學、極小數據、檢測有序性
希爾	O(n¹·³)~O(n log²n)	O(n²)	O(1)	否	中等數據量、嵌入式無法遞歸
快速	O(n log n)	O(n²)	O(log n)	否	通用大數據排序、庫函數首選

工程落地提示

C 標準庫 qsort 實現為快速排序變體，通用性最強。
C++ std::sort (IntroSort) = 快排 + 堆排序兜底 + 插入排序微優化，穩定版用 std::stable_sort (歸併排序)。
數據量 < 50 考慮插入排序；近乎有序用插入/冒泡；需要穩定用歸併/計數/基數排序。
避免遞歸棧溢出：大數據改用非遞歸棧模擬或改用堆排序/歸併排序。