11.10 泡沫排序法

sort 用了大半個單元，是時候拆開黑盒子——排序到底是怎麼「排」的？接下來三節介紹三種經典排序演算法，從最直觀的開始：泡沫排序法（Bubble Sort）。

¶原理：相鄰互換，最大的浮到最後

規則只有一條：由左到右檢查每一對相鄰的數，順序錯了（左邊比右邊大）就交換。把這條規則從頭到尾跑一輪，會發生一件妙事：最大的數一路被換到最右邊——它像汽水裡的泡泡一樣「浮」了上來，這就是名字的由來。

拿 6, 3, 2, 5, 4, 1 跑一輪：6 跟 3 換、跟 2 換、跟 5 換……一路換到底，變成 3, 2, 5, 4, 1, 6——6 就定位，之後不必再管最後一格。對剩下 n - 1 個數再跑一輪，第二大的數浮到倒數第二格……如此反覆，n - 1 輪之後全部就定位（最後剩一個數時它自動是最小的，不用再跑）：

¶完整程式碼

「交換相鄰兩數」用上冊 7.6 的 swap 恰到好處：

#include <iostream>
#include <algorithm>   // swap 住在這（上冊 7.6；用 bits/stdc++.h 的人不用管）
using namespace std;

const int MAX_N = 20005;
int a[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 共做 n - 1 輪；第 i 輪結束後，右邊 i 個位置已就定位
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (a[j] > a[j + 1]) {         // 左邊比右邊大：順序錯了
                swap(a[j], a[j + 1]);      // 交換這對鄰居
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}

執行結果（輸入 6 與 6 3 2 5 4 1）：

1 2 3 4 5 6

內層迴圈的上界 n - i 就是「就定位的不用再看」：第 1 輪檢查 n - 1 對、第 2 輪 n - 2 對……一輪比一輪短。

¶運算量：O(n²)

粗估：每輪最多檢查 n 對、共約 n 輪，所以大約 n \times n = n^2 次比較。精算的話，總檢查次數是

（等差級數求和，數學課的老朋友），大約是 n^2 的一半——量級仍是 O(n^2)。套上冊 4.9 的估計法（每秒約 10^9 次簡單運算）：n = 2 \times 10^4 時約 2 \times 10^8 次，勉強撐得住；n = 10^5 時約 5 \times 10^9 次，穩穩 TLE。對照 sort 的 10^6 毫無壓力——這就是為什麼實戰用 sort，泡沫排序學的是「排序可以怎麼辦到」的思路：它是最容易看懂、最容易手寫驗證的排序法，也是很多進階演算法課的起點。

動手試試看：泡沫排序有個經典小優化——某一輪從頭到尾一次交換都沒發生，代表已經全排好了，可以提前收工。加一個 bool 旗標（上冊 4.6 的旗標技巧）記錄本輪有沒有交換過，沒有就 break。拿「本來就排好」的輸入測試：原版跑滿 n - 1 輪，優化版第一輪結束就下班。