第 05 章 入門 約 8 分鐘
選擇排序：每次挑最小的放前面
從剩下的裡面挑最小的，放到最前面。動作簡單，但時間還是 O(n²)。
建議先看過： 04-insertion-sort
想像你在排隊伍
老師說「從矮到高排好」。你會怎麼做？
選擇排序的做法：每次掃過全班，找最矮的，叫他到第 1 個位置。然後第 2 矮的到第 2 個位置……
動手看一遍
排 [5, 3, 8, 1, 4]：
| 輪 | 找最小 | 跟誰換 | 結果 |
|---|---|---|---|
| 第 1 輪 | 1 | 跟位置 0 的 5 換 | [1, 3, 8, 5, 4] |
| 第 2 輪 | 3（已在對的位置） | 不換 | [1, 3, 8, 5, 4] |
| 第 3 輪 | 4 | 跟位置 2 的 8 換 | [1, 3, 4, 5, 8] |
| 第 4 輪 | 5（已對） | 不換 | [1, 3, 4, 5, 8] |
Pseudocode
Algorithm SelectionSort(A, n):
for i ← 0 to n-2:
minIdx ← i
for j ← i+1 to n-1:
if A[j] < A[minIdx]:
minIdx ← j
swap(A[i], A[minIdx])
複雜度
不管陣列原本長怎樣，都要跑 n²/2 次比較。所以：
| 情境 | Big-O |
|---|---|
| 最壞 | O(n²) |
| 平均 | O(n²) |
| 最好 | O(n²) — 也跑這麼多 |
⚠️跟前兩個排序比
選擇排序的最好情況也是 O(n²)，沒辦法像 Bubble / Insertion 那樣偵測已排序。 但好處：交換次數最少（最多 n-1 次），如果交換成本很貴（例如要寫硬碟），選擇排序反而划算。
📝考試會這樣考
比較題：寫出 Bubble / Insertion / Selection 三者在最壞、最好、平均的時間複雜度。
| 演算法 | 最壞 | 平均 | 最好 |
|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(n) |
| Insertion | O(n²) | O(n²) | O(n) |
| Selection | O(n²) | O(n²) | O(n²) ← 注意 |
這張表幾乎每次考試都會出，背起來吃豆腐。
這章記住
- 每輪挑剩下的最小，放到最前面。
- 不管資料長怎樣都是 O(n²)（這點輸給 Bubble / Insertion）。
- 優勢是交換次數最少（O(n)），冷知識但考試可能問。
學習進度只存在你的瀏覽器，不會上傳。