(Day 12) 氣泡排序 (Bubble Sort)
終於進入演算法的部分，預計會介紹 3~4 個很常見的排序演算法，所以光排序這個主題就會用掉 3~4 天的篇幅，今天除了介紹 Bubble Sort 外，會先簡單介紹一下排序，讓各位讀者更好地認識排序演算法。
(Day 13) 選擇排序 (Selection Sort)
目錄
選擇排序 (Selection Sort) 是一種簡單直觀的排序演算法。核心概念: 每一輪從尚未排序的元素中挑出最小 (或最大) 者，放到目前應在的位置，一直重複直到完成。可以把它想成「選拔賽」: 第一輪選出最優放第一名，第二輪從剩下的人選次優放第二名，依此類推。
演算法步驟
- 從索引 i = 0 開始，掃描區間 [i..n-1] 找到最小值的索引 min_idx，把 arr[i] 與 arr[min_idx] 交換。
- 將 i 前進一格，重複步驟 1，直到 i = n-1 為止。
- 全部就緒時，陣列即為遞增序。
由於每一輪至少能確定一個元素的最終位置，總共需要執行 n-1 輪。
範例說明
以序列 [29, 10, 14, 37, 13] 為例:
- 全陣列最小值是 10，與開頭 29 交換 → [10, 29, 14, 37, 13]
- 在剩餘 [29, 14, 37, 13] 中最小是 13，與 29 交換 → [10, 13, 14, 37, 29]
- 在剩餘 [14, 37, 29] 中最小是 14，位置不變 → [10, 13, 14, 37, 29]
- 在剩餘 [37, 29] 中最小是 29，與 37 交換 → [10, 13, 14, 29, 37]
- 完成
程式碼範例
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr = [29, 10, 14, 37, 13]
print(selection_sort(arr)) # 輸出: [10, 13, 14, 29, 37]
複雜度分析
時間複雜度
- 最佳情況: O(n^2)
- 最壞情況: O(n^2)
- 平均情況: O(n^2)
說明：即使資料本來已排序，外圈第 i 輪仍需在 [i..n-1] 全掃描以確認最小值，無法提前終止。
空間複雜度
- 額外空間：O(1)（原地排序，不需輔助結構）
穩定性
- 不穩定。因為「把最小值與前端元素交換」可能改變相同鍵值的相對次序。例：[4a, 5, 4b] 若選到的是後面的 4b 與前面的 4a 交換，排序後會變成 [4b, 5, 4a]，相對順序被打亂。
優缺點
| 面向 | 說明 |
|---|---|
| 優點 | 實作容易、流程清楚；原地排序 O(1)；每輪最多一次交換，交換成本低 |
| 缺點 | 無論資料狀態如何，掃描成本固定 → O(n^2)；不穩定 |
結語
選擇排序的價值在於思路清晰與交換成本低，雖然整體效率不佳 $O(n^2)$，但非常適合用來與其他基礎排序做對照:
- 和 Bubble 對比「交換策略」與是否能早停；
- 為 Insertion 鋪路，理解「已排序區/未排序區」的概念；
- 最後過渡到 O(n log n) 等級的演算法 (如 Merge/Quick)，理解為什麼在大規模資料上必須升級工具。