氣泡排序在做什麼
氣泡排序反覆比較相鄰的兩個數字：如果左邊比右邊大，就交換它們。
- 從最左邊開始，比較相鄰兩個數字，順序不對就交換。
- 一趟掃描下來，目前最大的數字就會被帶到最右邊，那個位置從此固定。
- 下一趟只需要掃描到還沒固定的範圍。
- 如果某一趟完全沒有發生交換，代表已經排好，可以提早結束。
為什麼是 O(n²)
n 個數字需要最多 n − 1 趟，每一趟最多比較 n − 1 次，加起來是 n(n − 1) / 2 次比較。完全反序時，每次比較都要交換，交換次數也是 n(n − 1) / 2，這就是上方「最差情況」顯示的數字。
資料已經排好時，第一趟沒有任何交換就結束，只需要 n − 1 次比較。
複雜度
| 最佳 | O(n) |
|---|---|
| 平均 | O(n²) |
| 最差 | O(n²) |
| 額外空間 | O(1) |
| 穩定 | 是 |
常見問題
- 為什麼叫氣泡排序？
- 每一趟都會把目前最大的數字一路交換到最右邊，就像氣泡浮到水面一樣。
- 氣泡排序最佳情況真的是 O(n) 嗎？
- 只有在加入「這一趟沒有交換就提早結束」的優化時才是。沒有這個優化，不管資料如何都是 O(n²)。這裡的動畫有加入該優化。
- 氣泡排序是穩定的嗎？
- 是。只有在左邊「嚴格大於」右邊時才交換，相等的值不會互換位置。