冒泡排序演算法：原理、優化版本與 C 語言完整實現

編輯：關於C語言

核心思想

重複走訪陣列，比較相鄰元素，順序錯誤則交換。每一輪最大（或最小）元素會像氣泡浮升至末端。共需 n-1 輪，第 i 輪只需比較前 n-i 個元素。

標準實現（升序）

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

優化 1：提前結束旗標

若某輪**完全無交換**，說明陣列已有序，可立即結束。

void bubble_sort_opt1(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 本輪無交換，已有序
    }
}

優化 2：記錄最後交換位置

最後一次交換位置之後的元素必定有序，下一輪只需掃描到該位置。

void bubble_sort_opt2(int arr[], int n) {
    int last_swap = n - 1;
    while (last_swap > 0) {
        int curr_swap = 0;
        for (int j = 0; j < last_swap; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                curr_swap = j;
            }
        }
        last_swap = curr_swap;
    }
}

完整可執行範例

#include 
#include 

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

int main() {
    int data[] = {-100, 79, -3, 0, 49, 21, 8, 200, 12341, 0};
    int n = sizeof(data) / sizeof(data[0]);

    print_arr(data, n, "原序：");
    bubble_sort_opt1(data, n);
    print_arr(data, n, "升序：");
    return 0;
}

複雜度分析

指標	數值	說明
時間複雜度（最佳）	O(n)	已有序，優化 1 觸發
時間複雜度（平均/最差）	O(n²)	逆序或隨機
空間複雜度	O(1)	原地排序
穩定性	穩定	相等元素不交換，相對順序不變

教學價值與實務建議

冒泡排序**極適合教學**：邏輯直觀、程式碼極短、易於驗證循環不變式。
**實務生產環境禁用**：O(n²) 效能無法接受，應改用 qsort (快速排序)、std::sort (IntroSort)、TimSort 等 O(n log n) 演算法。
極小陣列 (n < 50) 且極度接近有序時，優化版冒泡排序可能因常數因子極小而比快排略快，但極少見。