冒泡排序全解析：從基礎版到三級優化的 C++ 實現

基本原理

相鄰元素兩兩比較，逆序則交換。每輪將最大/最小元素「冒泡」到端點。穩定排序，時間 O(n²)。

版本一：雙層循環基礎版

void bubble1(int a[], int n) { // 正向
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n - i; j++)
            if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}
void bubble1r(int a[], int n) { // 反向
    for (int i = 1; i < n; i++)
        for (int j = n-1; j >= i; j--)
            if (a[j-1] > a[j]) swap(a[j-1], a[j]);
}

版本二：有序標記提前終止

若某輪無交換，說明已有序，直接跳出。

void bubble2(int a[], int n) {
    bool swapped = true;
    for (int i = 1; i < n && swapped; i++) {
        swapped = false;
        for (int j = 0; j < n - i; j++)
            if (a[j] > a[j+1]) { swap(a[j], a[j+1]); swapped = true; }
    }
}

版本三：記錄最後交換位置，縮小下輪範圍

最後一次交換位置 k 之後的元素已有序，下輪只需掃描到 k。

void bubble3(int a[], int n) {
    int bound = n - 1;
    while (bound > 0) {
        int lastSwap = 0;
        for (int j = 0; j < bound; j++)
            if (a[j] > a[j+1]) { swap(a[j], a[j+1]); lastSwap = j; }
        if (lastSwap == 0) break; // 本輪無交換
        bound = lastSwap;
    }
}

交換函數：異或交換 (無臨時變量)

void swap(int& a, int& b) {
    if (a != b) { a ^= b; b ^= a; a ^= b; }
}

優化效果對比

測試主程序

int main() {
    vector a = {64, 34, 25, 12, 22, 11, 90};
    bubble3(a.data(), a.size());
    for (int x : a) cout << x << ' ';
    return 0;
}

總結

冒泡排序雖非工程首選（std::sort 更快），但其三級優化思路——標記提前退出、記錄邊界縮小範圍——體現了「利用問題特性減少無效比較」的算法設計智慧。理解這三個版本，有助於掌握插入排序、快速排序等更高級算法的優化靈感來源。