冒泡排序演進：從初級版到優化版的完整推導與複雜度分析

核心思想

冒泡排序屬於交換排序，基本思想：兩兩比較相鄰記錄，順序錯誤則交換。較小元素如氣泡般逐漸「浮」到序列頂端，故名。

三個版本演進

版本一：初級交換排序（非標準冒泡）

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

缺陷：不滿足「相鄰比較」特徵，實質是選擇排序變體。每輪將最小值交換到第 i 位。

版本二：標準冒泡排序

void BubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n-1-i; j++)  // 或 j=n-2; j>=i; j-- 方向相反
            if (arr[j+1] < arr[j]) swap(arr[j], arr[j+1]);
}

特徵：相鄰比較交換。每輪結束，最大值「沉」底或最小值「浮」頂。比較次數固定：n(n-1)/2。

版本三：優化版（早期終止）

void BubbleSort(int arr[], int n) {
    bool flag = true;
    for (int i = 0; i < n && flag; i++) {
        flag = false;
        for (int j = 0; j < n-1-i; j++)
            if (arr[j+1] < arr[j]) {
                swap(arr[j], arr[j+1]);
                flag = true;  // 發生交換，標記需繼續
            }
    }
}

優化點：若某輪無交換，說明已有序，立即終止外層循環。

複雜度深度分析

教學價值總結

• 理解「相鄰比較交換」核心模式
• 掌握「有序檢測早期終止」優化思想
• 為學習快速排序（冒泡的本質改進）鋪墊
• 穩定排序，適合教學演示與極小規模數據

雖實戰罕用，但冒泡排序是理解排序算法演進邏輯的關鍵階梯。