你有沒有想過，怎麼把一堆亂糟糟的數字按順序排好？比如把 [5, 3, 8, 4, 2] 變成 [2, 3, 4, 5, 8]？今天我們要學的冒泡排序，就是最簡單的排序方法之一，3分鐘就能入門！
什麼是冒泡排序？¶
想象一下，水中的氣泡會從水底慢慢浮到水面。冒泡排序的名字就來源於這個“氣泡上浮”的過程：每一次遍歷數組，都會讓最大的元素像氣泡一樣“冒”到數組的末尾，最終完成排序。
舉個例子：如果我們要把數字從小到大排序，冒泡排序會讓大的數字“往後跑”，小的數字“往前擠”，就像氣泡在水裏上浮一樣。
冒泡排序的核心思想¶
- 重複比較相鄰元素：從數組的第一個元素開始，依次比較相鄰的兩個元素，如果前一個元素比後一個大，就交換它們的位置。
- “氣泡”逐步上浮：每完成一輪遍歷，最大的元素會“冒”到數組的最後一個位置（正確位置），所以下一輪可以少比較一次（不需要再管最後一個元素）。
- 提前結束條件：如果某一輪遍歷中沒有發生任何交換，說明數組已經完全有序，排序可以提前結束。
具體步驟（以 [5, 3, 8, 4, 2] 爲例）¶
我們用一個數組 [5, 3, 8, 4, 2] 演示排序過程，目標是從小到大排列。
第1輪：讓最大的數“冒”到末尾¶
- 從第一個元素開始比較：
- 比較
5和3：5 > 3，交換 →[3, 5, 8, 4, 2] - 比較
5和8：5 < 8，不交換 → 不變 - 比較
8和4：8 > 4，交換 →[3, 5, 4, 8, 2] - 比較
8和2：8 > 2，交換 →[3, 5, 4, 2, 8] - 結果：最大的數
8已“冒”到末尾，數組變爲[3, 5, 4, 2, 8]。
第2輪：讓第二大的數“冒”到倒數第二位置¶
- 因爲
8已排好，所以這一輪只需比較前4個元素： - 比較
3和5：3 < 5，不交換 - 比較
5和4：5 > 4，交換 →[3, 4, 5, 2, 8] - 比較
5和2：5 > 2，交換 →[3, 4, 2, 5, 8] - 結果：第二大的數
5已“冒”到倒數第二位置，數組變爲[3, 4, 2, 5, 8]。
第3輪：讓第三大的數“冒”到倒數第三位置¶
- 只需比較前3個元素：
- 比較
3和4：3 < 4，不交換 - 比較
4和2：4 > 2，交換 →[3, 2, 4, 5, 8] - 結果：第三大的數
4已“冒”到倒數第三位置，數組變爲[3, 2, 4, 5, 8]。
第4輪：讓第四大的數“冒”到倒數第四位置¶
- 只需比較前2個元素：
- 比較
3和2：3 > 2，交換 →[2, 3, 4, 5, 8] - 結果：第四大的數
3已“冒”到倒數第四位置，數組變爲[2, 3, 4, 5, 8]。
第5輪：檢查是否有序（提前結束）¶
- 此時數組
[2, 3, 4, 5, 8]已經完全有序，若再遍歷一次： - 比較
2和3、3和4、4和5、5和8，均無交換。 - 結論：排序完成。
關鍵優化：提前結束¶
如果某一輪遍歷中沒有發生任何交換，說明數組已經有序，不需要繼續排序。例如，如果數組本身接近有序（如 [1, 3, 2, 4, 5]），冒泡排序會在第二輪就提前結束，減少不必要的比較。
時間複雜度與空間複雜度¶
- 時間複雜度：最壞情況下（數組完全逆序）需要
n²次比較和交換，平均情況也是O(n²)（n爲數組長度）。 - 空間複雜度：僅需要常數級額外空間（如交換用的臨時變量），所以是
O(1)。
總結¶
冒泡排序的精髓在於“比較相鄰元素並交換”，像氣泡一樣逐步將大元素“冒”到末尾。它簡單易懂、容易實現，是理解排序算法的絕佳入門工具。雖然效率較低（適合小規模數據），但通過它你能掌握排序的核心邏輯，爲學習更復雜的算法（如快速排序、歸併排序）打下基礎。
試着手動實現一個冒泡排序，從數組 [6, 1, 7, 3, 2] 開始，相信你很快就能上手！