冒泡排序算法原理與 C 語言實現優化全解析

編輯：關於C語言

算法思想

冒泡排序 通過重複遍歷待排序數列，比較相鄰元素並交換順序錯誤的對，使較大（或較小）的元素像氣泡一樣逐步「浮」到數列末端。經過 n-1 輪遍歷後，數列有序。

基本實現（雙層循環）

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 第 i 輪，確定第 n-i-1 位置的最終值
        for (int j = 0; j < n - i - 1; j++) {  // 相鄰比較交換
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

關鍵優化：提前終止標誌

若某輪遍歷未發生任何交換，說明數列已有序，可立即結束：

void bubble_sort_opt(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            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 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; // 下一輪邊界
    }
}

複雜度分析

指標	數值	說明
最好時間複雜度	O(n)	已有序數列，優化版單趟遍歷即結束
平均/最壞時間複雜度	O(n²)	逆序數列需完整比較交換
空間複雜度	O(1)	原地排序，僅需常數臨時變量
穩定性	穩定	相等元素不交換，相對順序不變

完整可運行示例

#include <stdio.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 - i - 1; j++) {
            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_arr(const int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int a[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(a) / sizeof(a[0]);
    printf("排序前: "); print_arr(a, n);
    bubble_sort(a, n);
    printf("排序後: "); print_arr(a, n);
    return 0;
}

教學與工程建議

教學場景：冒泡排序代碼簡短、邏輯直觀，適合初學者理解「比較交換」「原地排序」「穩定性」等基本概念。
工程場景：嚴禁用於大數據量。小規模（< 50）、近乎有序數據可考慮優化版；通用排序請用 qsort (C 標準庫)、std::sort (C++)、Timsort (Python/Java) 等 O(n log n) 算法。
面試重點：能手寫基本版、解釋優化思路、分析複雜度、說明穩定性、對比插入/選擇排序適用場景。