以前在前端寫 Code 的時候，我其實完全沒有想過「排序的底層到底是怎麼運作的」。
例如要處理一組資料，我可能就是使用 for 迴圈把資料一個一個拿出來比較，或是直接使用 JavaScript 提供的 sort()。直到開始接觸演算法之後才發現，原來「排序」這件事情也有很多不同的做法。
| 演算法 | 最差時間複雜度 | 最佳時間複雜度 | 平均時間複雜度 | 空間複雜度 |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Bubble Sort | O(n²) | O(n) | O(n²) | O(1) |
| Insertion Sort | O(n²) | O(n) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n²) | O(n log n) | O(n log n) | 視實作而定 |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
表格資料參考來源：MagicLen〈常見排序演算法〉。
今天先從 Bubble Sort（氣泡排序） 開始理解吧～
我目前對 Bubble Sort 最簡單的理解就是三件事情：
比較 → 交換 → 重複
假設現在有一組數字：
[5, 3, 8, 1]
我們要把它按照「由小到大」排列。
Bubble Sort 會從最前面開始，每次比較相鄰的兩個數字。
[5, 3, 8, 1] → [3, 5, 8, 1]
5 > 3，所以交換。
[3, 5, 8, 1] → [3, 5, 8, 1]
5 < 8，所以不交換。
[3, 5, 8, 1] → [3, 5, 1, 8]
8 > 1，所以交換。
這時候我才理解 Bubble Sort 很重要的一個特性：
每完成一輪比較，這一輪最大的數字就會一路被交換到最右邊。
所以第一輪結束後，8 已經確定在正確的位置，下一輪就不用再比較它。
[3, 5, 1, 8] → [3, 5, 1, 8]
3 < 5，不交換。
[3, 5, 1, 8] → [3, 1, 5, 8]
5 > 1，交換。
[3, 1, 5, 8] → [1, 3, 5, 8]
3 > 1，交換。
最後就得到：
[1, 3, 5, 8]
原本我以為排序就是「把每個數字拿出來比大小」，但 Bubble Sort 讓我開始理解，演算法描述的不只是「要比較」，還包含了要怎麼比較、什麼情況交換，以及這個流程要重複到什麼時候。
Bubble Sort 的核心其實可以濃縮成：
相鄰兩個數字進行比較 → 順序錯誤就交換 → 持續重複。
而每跑完一輪，就會有一個較大的數字慢慢「浮」到右邊，這也是 Bubble Sort 這個名字很形象的地方。
MagicLen，〈常見排序演算法〉
https://magiclen.org/sorting-algorithm/
MagicLen，〈氣泡排序法（Bubble Sort）演算法，容易實作的穩定排序演算法〉
https://magiclen.org/bubble-sort/
iThome鐵人賽
看影片追技術