最好懂的排序法 —— 相鄰兩個兩個比,大的往後換,最大的像泡泡一樣浮到最後。
老實說——實務上幾乎不用。它是 O(n²),資料一多就慢。但它是理解排序的最佳入門:邏輯超直覺,而且能讓你親眼看到「巢狀迴圈 = O(n²)」長什麼樣子。學會它,之後的合併排序、快速排序才知道「快在哪」。
1. 從頭走到尾,把相鄰的兩個拿來比。
2. 左邊比右邊大 → 交換,讓大的往右移。
3. 一整輪跑完,這輪最大的一定被推到最右邊,定位完成。
4. 對「還沒定位」的部分重複,每輪範圍縮一格。優化:某一輪完全沒發生交換,代表已經排好,可以提早收工。
大泡泡浮得快,每一輪最大的先冒到頂端——名字就是這樣來的。
相鄰兩人比高矮,順序不對就換位,一輪一輪把最高的擠到隊尾。
從左看到右,遇到左大右小就對調,反覆掃到不用再換為止。
紫色是正在比較的一對、紅色代表剛剛發生交換、綠色是已排好定位的。按「下一步」慢慢看,或按「自動播放」讓它跑給你看。
外層要跑大約 n 輪(每輪定位一個),內層每輪又要比大約 n 次。n 乘 n,就是 O(n²)。所以資料量變兩倍,工作量會變成大約四倍:
這就是為什麼真正要排大量資料時,會改用 O(n log n) 的合併排序或快速排序。
從最基本的版本,到優化、變形(雞尾酒排序、遞迴版),再到穩定性與效率分析。
❌ 內層範圍沒縮 —— 寫成 range(n - 1) 而不是 range(n - 1 - i),雖然結果對,但每輪都重比已排好的部分,白做工。
❌ 交換寫錯 —— Python 用 a, b = b, a 一行交換最安全;分兩行寫容易把值蓋掉。
❌ 以為它很快 —— 氣泡排序是教學用的,拿去排幾萬筆資料會慢到懷疑人生,實務請用內建 sorted()。
[3, 1, 2],第一輪跑完(比完所有相鄰對)後,陣列會變成什麼?O(n)?> 改成 >=,排序結果會變嗎?那「穩定性」會變嗎?把答案打到對話裡,我幫你對。