冒泡排序 C++ 實現與優化變體對比

算法原理

冒泡排序通過重複遍歷數組，比較相鄰元素並交換逆序對，將最大元素像氣泡一樣「浮」到末尾。每輪遍歷確定一個元素的最終位置。

版本一：標準單向冒泡

void bubbleSort(vector& a) {
    int n = a.size();
    for (int i = 0; i < n-1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n-1-i; ++j) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前終止優化
    }
}

• 外層 $n-1$ 輪，內層每輪縮短 1。
• swapped 標記：若某輪無交換，說明已有序，提前退出。

版本二：雙向冒泡（雞尾酒排序 / Cocktail Shaker Sort）

奇數輪正向冒泡（大元素右移），偶數輪反向冒泡（小元素左移）。同時縮減左右邊界。

void cocktailSort(vector& a) {
    int n = a.size();
    int left = 0, right = n - 1;
    while (left < right) {
        bool swapped = false;
        // 正向：大元素右移
        for (int i = left; i < right; ++i)
            if (a[i] > a[i+1]) { swap(a[i], a[i+1]); swapped = true; }
        if (!swapped) break;
        --right; // 最大元素已就位
        
        // 反向：小元素左移
        swapped = false;
        for (int i = right; i > left; --i)
            if (a[i-1] > a[i]) { swap(a[i-1], a[i]); swapped = true; }
        if (!swapped) break;
        ++left; // 最小元素已就位
    }
}

性能對比（$n=2000$ 隨機數組）

雙向冒泡約快 30%，但仍屬 $O(n^2)$，僅適合教學或極小數據量（$n \le 50$）。

複雜度總結

空間複雜度 $O(1)$，穩定排序。

實戰建議

1. 生產代碼**永遠使用** std::sort（IntroSort：快速+堆+插入混合，$O(n \log n)$ 保證）。
2. 教學/面試掌握：單向/雙向/遞歸/標記優化四種寫法。
3. 極小數組（$n \le 16$）插入排序常比冒泡更快，std::sort 內部也會切換到插入排序。

完整可運行示例

#include 
using namespace std;

void bubbleSort(vector& a) { /* 版本一 */ }
void cocktailSort(vector& a) { /* 版本二 */ }

int main() {
    vector a = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(a);
    for (int x : a) cout << x << ' '; // 11 12 22 25 34 64 90
    cout << '\n';
    
    vector b = {64, 34, 25, 12, 22, 11, 90};
    cocktailSort(b);
    for (int x : b) cout << x << ' '; // 11 12 22 25 34 64 90
    return 0;
}