冒泡排序算法原理與 C 語言實現詳解

編輯：關於C語言

冒泡排序算法原理與 C 語言實現詳解

冒泡排序是最基礎的交換排序算法，通過相鄰元素比較交換，將大元素像氣泡一樣逐步「冒」到序列末端。本文系統講解算法邏輯、運作過程、時間複雜度、穩定性分析，並提供標準 C 實現代碼。

算法基本思想

重複遍歷序列，比較相鄰兩個元素，若順序錯誤（前大後小）則交換。每輪遍歷將當前未排序部分的最大元素移動到正確位置。直到某輪無任何交換，說明已有序。

運作過程圖解（以升序為例）

初始: [5, 1, 4, 2, 8]
第1輪: 比較(5,1)→交換 [1,5,4,2,8]
        比較(5,4)→交換 [1,4,5,2,8]
        比較(5,2)→交換 [1,4,2,5,8]
        比較(5,8)→不交換 → 最大值8已歸位
第2輪: 對前4個元素重複 → 5歸位
第3輪: 對前3個元素重複 → 4歸位
第4輪: 對前2個元素重複 → 2歸位
完成: [1, 2, 4, 5, 8]

時間複雜度分析

情況	比較次數	交換/移動次數	時間複雜度
最好（已有序）	n-1	0	O(n)
最壞（逆序）	n(n-1)/2	3n(n-1)/2	O(n²)
平均	~n²/4	~3n²/4	O(n²)

**優化**：設置標誌位，若某輪無交換則提前終止，使最好情況達到 O(n)。

穩定性證明

冒泡排序**只交換相鄰元素**，且**僅在嚴格大於時交換**（`a[i] > a[i+1]`）。相等元素不交換，相對順序不變。因此冒泡排序是**穩定排序算法**。

標準 C 語言實現

#include <stdio.h>

#define SIZE 8

void bubble_sort(int a[], int n) {
    int i, j, temp;
    // 外層控制輪數，共 n-1 輪
    for (j = 0; j < n - 1; j++) {
        // 內層對未排序部分兩兩比較，範圍逐輪縮小
        for (i = 0; i < n - 1 - j; i++) {
            if (a[i] > a[i + 1]) { // 升序：前大後小則交換
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

int main() {
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;

    printf("排序前: ");
    for (i = 0; i < SIZE; i++) printf("%d ", number[i]);
    printf("\n");

    bubble_sort(number, SIZE);

    printf("排序後: ");
    for (i = 0; i < SIZE; i++) printf("%d ", number[i]);
    printf("\n");
    return 0;
}

優化版：早退出機制

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