您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 更多程式設計知識

C 語言經典氣泡排序法：優化版、遞迴版與效能分析

編輯：更多程式設計知識

基本氣泡排序 (Bubble Sort)


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_opt(int *arr, int n) {
    bool swapped;
    do {
        swapped = false;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
        --n; // 最後一個已是最大，下輪少比較
    } while (swapped);
}

優化 2：記錄最後交換位置 (縮小掃描範圍)


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

遞迴版本 (教學用)


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

效能分析

最佳情況發生於**已排序陣列**，旗標版本只需一趟掃描即結束。

實測數據 (n=10,000, 隨機整數, GCC -O2)


基本版本        : 1.84 秒
旗標優化        : 1.02 秒
記錄最後交換    : 0.67 秒
qsort (stdlib)  : 0.003 秒

何時使用氣泡排序

教學示範排序基本概念
資料量極小 (n < 50) 且**近乎有序**
嵌入式系統記憶體極限，程式碼體積優先 (基本版本僅 ~10 行)
**絕不**用於生產環境大量資料排序

現代替代：`qsort` / `std::sort`


// C 標準庫
#include 
int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }
qsort(arr, n, sizeof(int), cmp);

// C++
#include 
std::sort(arr, arr + n);