C 語言數組排序算法大全：冒泡、選擇、快速、插入、希爾

排序是程序設計的基礎功。本文系統整理五種經典排序算法的原理、代碼實現與性能對比，適合初學者建立完整知識框架。

測試數據

int a[] = {13, 0, 5, 8, 1, 7, 21, 50, 9, 2}; // 長度 10

1. 冒泡排序

思想：兩兩比較相鄰元素，大的「冒泡」到右端。每輪將最大值移至末尾。

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

• 時間：O(n²)
• 交換次數多，效率低
• 穩定

2. 選擇排序

思想：每輪在未排序區找最小值，與首位交換。減少不必要的交換。

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

• 時間：O(n²)
• 交換次數 ≤ n-1，優於冒泡
• 不穩定

3. 快速排序

思想：分治法。選基準，小者左、大者右，遞歸處理子區間。

void quick(int *a, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = a[(left + right) / 2];
    do {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++; j--;
        }
    } while (i <= j);
    if (left < j) quick(a, left, j);
    if (i < right) quick(a, i, right);
}

• 平均時間：O(n log n)
• 最壞：O(n²)（可用隨機基準或三數取中優化）
• 不穩定、原地排序

4. 插入排序

思想：維護有序前綴，將新元素插入適當位置（類似整理撲克牌）。

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

• 時間：O(n²)，最好 O(n)（已有序）
• 穩定、適應性強、在線算法

5. 希爾排序

思想：插入排序改進版。按間隔 gap 分組排序，逐步縮小 gap 至 1。

void shell(int *a, int n) {
    for (int gap = n / 2; gap >= 1; gap /= 2)
        for (int i = gap; i < n; i++) {
            int tmp = a[i], j = i - gap;
            while (j >= 0 && tmp < a[j]) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = tmp;
        }
}

• 時間：O(n^1.3)~O(n²)，視 gap 序列而定
• 不穩定，但對中等規模數據極快

統一測試主程序

#include 

void print(int *a, int n) {
    for (int i = 0; i < n; i++) printf("%5d", a[i]);
    puts("");
}

int main() {
    int a1[] = {13,0,5,8,1,7,21,50,9,2};
    int a2[] = {13,0,5,8,1,7,21,50,9,2};
    int a3[] = {13,0,5,8,1,7,21,50,9,2};
    int a4[] = {13,0,5,8,1,7,21,50,9,2};
    int a5[] = {13,0,5,8,1,7,21,50,9,2};

    printf("原始: "); print(a1, 10);

    bubble(a1, 10); printf("冒泡: "); print(a1, 10);
    choose(a2, 10); printf("選擇: "); print(a2, 10);
    quick(a3, 0, 9); printf("快速: "); print(a3, 10);
    insert(a4, 10); printf("插入: "); print(a4, 10);
    shell(a5, 10); printf("希爾: "); print(a5, 10);

    return 0;
}

性能對比總結

進階延伸

• 歸並排序：O(n log n) 穩定，需 O(n) 額外空間，外部排序基石
• 堆排序：O(n log n) 原地，不穩定，優先隊列實現基礎
• 計數/基數/桶排序：非比較排序，O(n) 線性時間，適用特定數據範圍
• std::sort / qsort：工程實踐首選，Introsort（快速+堆+插入混合）

結語

理解各排序算法的權衡，比死記代碼更重要。實際工程中，除非有特殊約束，優先使用標準庫 qsort/std::sort；面試與教學場景下，熟練手寫快速、歸並、堆排序是基本功。