選擇排序在做什麼
選擇排序每一輪都從「還沒排好」的範圍中選出最小值，放到這個範圍的最前面。
- 先假設範圍的第一個數字是最小值。
- 由左到右掃描剩下的數字，遇到更小的就更新最小值。
- 掃描完畢，把最小值與範圍的第一個數字交換。
- 範圍縮小一格（左邊那格已排好），重複直到只剩一個數字。
和插入排序、氣泡排序的差別
選擇排序的比較次數固定，與資料無關；但它的交換次數很少。切換不同的預設資料，你會看到比較次數永遠是 n(n − 1) / 2，而交換次數最多是 n − 1。
複雜度
| 最佳 | O(n²) |
|---|---|
| 平均 | O(n²) |
| 最差 | O(n²) |
| 額外空間 | O(1) |
| 穩定 | 否 |
常見問題
- 為什麼選擇排序最佳情況也是 O(n²)？
- 因為它每一輪都必須掃描完剩下的所有數字才能確定最小值，不管資料是否已排好，比較次數都是 n(n − 1) / 2。
- 選擇排序有什麼優點？
- 交換次數最多只有 n − 1 次。當「寫入」的成本遠高於「比較」時，它有機會比其他 O(n²) 排序划算。
- 選擇排序是穩定的嗎？
- 不是。把最小值交換到前面時，可能讓原本相等的兩個值改變相對順序。