氣泡排序演算法 C++ 實作與逐輪交換過程圖解

氣泡排序是最經典的入門排序演算法，透過相鄰元素兩兩比較交換，將大值逐步「沉底」、小值「浮起」。本文提供逐輪過程圖解、標準實作與優化版本。

逐輪交換過程圖解（升序）

初始: 10 3 8 0 6 9 2
第 1 輪: 3 8 0 6 9 2 10  (10 沉至最右)
第 2 輪: 3 0 6 8 2 9 10  (9 定位)
第 3 輪: 0 3 6 2 8 9 10  (8 定位)
第 4 輪: 0 3 2 6 8 9 10  (6 定位)
第 5 輪: 0 2 3 6 8 9 10  (3 定位)
第 6 輪: 0 2 3 6 8 9 10  (無交換，提前結束)

標準 C++ 實作

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {2, 4, 1, 0, 8, 4, 8, 9, 20, 7};
    BubbleSort(arr, 10);
    for (int v : arr) cout << v << ' ';  // 0 1 2 4 4 7 8 8 9 20
}

優化版：提前結束旗標

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

複雜度與特性

教學與實務定位

• 教學價值極高：邏輯直觀、易於理解「比較-交換」核心、適合引入優化思維。
• 實務極少直接使用：N > 50 時效能遠遜於快速排序/歸併/堆積排序。
• 極小規模（N ≤ 10）且近乎有序資料，優化版氣泡排序偶爾具優勢（常數因子極小、無遞迴/函式呼叫開銷）。

總結

氣泡排序是演算法入門的「Hello World」，掌握其「相鄰比較交換、大值沉底」直觀模型與「提前結束」優化技巧，為學習更高階排序奠定基礎。