C 語言經典排序算法實現與複雜度深度分析：冒泡、交換、選擇、快排全解析

排序算法分類與複雜度總覽

一、簡單排序算法（O(N²)）

1. 冒泡排序

核心思想：相鄰元素兩兩比較，大的「冒泡」到右端。每輪將當前最大值固定到末尾。

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

性能分析：

• 比較次數固定：Σ(i=1 to n-1) (n-i) = n(n-1)/2 = O(N²)
• 交換次數：逆序滿交換（O(N²)），正序零交換（O(1)），平均 O(N²/4)
• 可優化：加標誌位檢測本輪無交換則提前結束（最好 O(N)）

2. 交換排序（選擇排序變體）

核心思想：第 i 輪，用 a[i] 與後續所有元素比較，發現更小即交換。最終 a[i] 為當前最小值。

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

比較次數同冒泡 O(N²)，交換次數略多（每次發現更小即交換），實際較慢。

3. 選擇排序

核心思想：第 i 輪，掃描未排序區找到最小值索引 minIdx，**僅交換一次** a[i] 和 a[minIdx]。

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

優勢：交換次數固定 N-1（O(N)），適合**寫入成本高**（如 Flash、EEPROM）場景。

二、高級排序：快速排序（O(N log N)）

核心思想：分治法。選基準，分區使左側 ≤ 基準 ≤ 右側，遞歸排序子區。

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

關鍵優化：

• 三數取中法選基準（首、中、尾中位數）
• 小區間（<10）改用插入排序
• 尾遞歸優化 / 顯式棧避免棧溢出

三、特殊視角算法（教學/趣味）

希爾排序

插入排序改進：按增量分組插入，逐步縮小增量至 1。打破 O(N²) 下界，實際極快。

堆排序

利用最大堆特性，每次取堆頂與末尾交換，再調整堆。保證 O(N log N) 最壞情況，原地排序。

工程選型指南

C 標準庫 qsort 使用示例

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }
qsort(arr, n, sizeof(int), cmp);

總結

理解排序算法不僅是背誦代碼，更要掌握：**複雜度推導、穩定性、適應性、空間權衡、實際常數因子**。「簡單排序」用於教學與微小數據，「快速排序」是工程首選，「歸併/堆/希爾」解決特定約束。實際開發中**優先使用標準庫**，僅在極端約束下手寫優化。