C語言冒泡排序算法詳解：原理、優化實現與完整代碼示例

冒泡排序是最基礎的排序算法之一，雖然平均/最壞時間複雜度為 O(n²)，但其思路直觀、代碼簡潔，適合教學與小規模數據排序。本文通過圖解演示排序過程，給出生產級優化代碼（含提前終止標誌），並分析算法特性。

核心思想：氣泡上浮

將數組視為垂直排列，每趟從底部向上比較相鄰元素，**逆序則交換**。每趟結束時，最小元素像氣泡一樣「浮」到當前未排序區域的最頂端。共需 n-1 趟，依次將最小、次小、第三小……元素移至第 0、1、2……位置。

圖解演示（以 8 元素為例）

初態:  38  20  46  38  74  91  12  25
第1趟: 12  38  20  46  38  74  91  25  ← 12 浮到頂端
第2趟: 12  20  38  25  46  38  74  91  ← 20 就位
第3趟: 12  20  25  38  38  46  74  91  ← 25 就位
第4趟: 12  20  25  38  38  46  74  91  ← 無交換，提前結束

優化版 C 實現（含 Flag 提前終止）

#include <stdio.h>
#include <stdbool.h>

/* 冒泡排序：升序排列 r[0..n-1] */
void bubble_sort(int r[], int n) {
    int i, j, temp;
    bool swapped;           // 標誌本趟是否發生交換
    for (i = 0; i < n - 1; ++i) {
        swapped = false;
        for (j = n - 1; j > i; --j) {  // 從底部向上冒泡
            if (r[j] < r[j - 1]) {
                temp = r[j];
                r[j] = r[j - 1];
                r[j - 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 本趟無交換 → 已有序，提前退出
    }
}

/* 打印數組 */
void print_array(const int r[], int n) {
    for (int i = 0; i < n; ++i) printf("%4d", r[i]);
    putchar('\n');
}

int main(void) {
    int a[] = {38, 20, 46, 38, 74, 91, 12, 25};
    int n = sizeof(a) / sizeof(a[0]);
    printf("排序前: "); print_array(a, n);
    bubble_sort(a, n);
    printf("排序后: "); print_array(a, n);
    return 0;
}

關鍵點解析

算法複雜度與特性

• 時間複雜度：最好 O(n)（已有序）、平均/最壞 O(n²)。
• 空間複雜度：O(1)，原地排序。
• 穩定性：穩定（相等元素不交換，相對順序不變）。
• 適用場景：教學、極小數據集（n < 50）、近乎有序數據（配合 flag 極快）。

常見變體

• 雞尾酒排序：雙向冒泡，減少「烏龜」（大元素在右端）移動慢的問題。
• 歸併/快速/堆排序：大數據量首選 O(n log n) 算法。