數據結構：C語言實現冒泡排序（Bubble Sort）完整教學

冒泡排序核心思想

冒泡排序通過重複遍歷數組，比較相鄰元素並交換順序錯誤的元素，較大元素像氣泡一樣逐步「浮」到數組末端。

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 穩定排序：相等元素相對位置不變

標準實現（優化版：含提前終止標記）

#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // 優化：若本輪無交換，說明已有序
        for (int j = 0; j < n - 1 - i; j++) {  // 最後 i 個已有序
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 提前終止
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {22, 11, 5, 666, 3, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: "); print_array(arr, n);
    bubble_sort(arr, n);
    printf("排序後: "); print_array(arr, n);
    return 0;
}

執行流程圖解（以 {22, 11, 5, 666, 3, 6, 8} 為例）

第 1 輪（將最大值 666 冒泡到末尾）：

[22, 11, 5, 666, 3, 6, 8]
 → [11, 22, 5, 666, 3, 6, 8]  (22>11 交換)
 → [11, 5, 22, 666, 3, 6, 8]  (22>5 交換)
 → [11, 5, 22, 666, 3, 6, 8]  (22<666 無交換)
 → [11, 5, 22, 3, 666, 6, 8]  (666>3 交換)
 → [11, 5, 22, 3, 6, 666, 8]  (666>6 交換)
 → [11, 5, 22, 3, 6, 8, 666]  (666>8 交換)  ✓ 666 就位

後續輪次類似，逐步將 22、11、8... 移至正確位置。

關鍵優化點

1. 內層範圍遞減：`j < n-1-i`，避免比較已排序尾部
2. 提前終止標記：`swapped` 旗標，最好情況 O(n)（已有序數組）
3. 雙向冒泡（雞尾酒排序）：左右交替，進一步減少輪次

雙向冒泡排序（Cocktail Shaker Sort）實現

void cocktail_sort(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        // 左→右：冒最大值到 right
        for (int i = left; i < right; i++)
            if (arr[i] > arr[i+1]) swap(arr[i], arr[i+1]);
        right--;
        // 右→左：冒最小值到 left
        for (int i = right; i > left; i--)
            if (arr[i] < arr[i-1]) swap(arr[i], arr[i-1]);
        left++;
    }
}

三大基礎排序對比總結

| 特性 | 冒泡排序 | 選擇排序 | 插入排序 | |------|----------|----------|----------| | 平均時間 | O(n²) | O(n²) | O(n²) | | 最好情況 | **O(n)** | O(n²) | **O(n)** | | 最壞情況 | O(n²) | O(n²) | O(n²) | | 穩定性 | **穩定** | 不穩定 | **穩定** | | 交換/移動次數 | O(n²) | **O(n)** | O(n²) | | 適合場景 | 教學、近乎有序數據 | 寫入代價高 | 小規模/近乎有序 |

教學價值

冒泡排序雖非工業級首選，但其相鄰比較交換的直觀邏輯、穩定性特性、以及提前終止優化的思想，是理解更複雜排序（如快速排序分區、希爾排序間隔）的重要基石。