前言：選擇排序的極簡哲學
選擇排序核心邏輯：**每輪在第 i 小元素中選出最小者，放入第 i 位置**。不像插入/交換排序依賴資料分佈，選擇排序比較次數固定、移動次數最少，是「寫入成本極高」場景的理論最優解。
一、直接選擇排序實作
template <class T>
void SelectSort(T a[], int N, int& KCN, int& RMN) {
KCN = RMN = 0;
for (int i = 0; i < N; ++i) {
int k = i; // 假設當前位置最小
for (int j = i+1; j < N; ++j) // 掃描未排區間
if (++KCN && a[j] < a[k]) k = j; // 記錄最小元素索引
if (k != i) { swap(a[k], a[i]); RMN += 3; } // 僅最小元素與當前位置交換
}
}
二、效能測試：KCN 固定、RMN 極小
| 輸入 | N=10,000 時間 | KCN | KCN/N² | RMN | RMN/N |
|---|
| 升序 | 721ms | 49,995,000 | 0.50 | 0 | 0 |
| 隨機 | 711ms | 49,995,000 | 0.50 | 29,955 | 3.0 |
| 降序 | 711ms | 49,995,000 | 0.50 | 15,000 | 1.5 |
三大鐵律
- KCN 恆定：N(N-1)/2 ≈ 0.5 N²，完全不受資料分佈影響
- RMN 極小：最多 3(N-1) 次移動，理論最少寫入
- 時間穩定：三種輸入時間差異 < 2%（測試誤差範圍）
三、選擇排序 vs 其他 O(N²) 排序
| 指標 | 選擇排序 | 插入排序 | 氣泡排序 |
|---|
| 比較次數 | 固定 0.5N² | 最佳 N，最壞 0.5N² | 最佳 N，最壞 0.5N² |
| 移動次數 | 最少 3N | 最佳 0，最壞 0.5N² | 最佳 0，最壞 1.5N² |
| 穩定性 | 不穩定 | 穩定 | 穩定 |
| 適應性 | 無 | 強（近乎有序極快） | 中（有優化標記） |
| 寫入敏感場景 | ⭐⭐⭐⭐⭐ | ⭐⭐ | ⭐ |
四、不穩定性示例
// 輸入：5a, 5b, 3 (5a 在 5b 前)
// 第一輪選出 3，與 5a 交換
// 結果：3, 5b, 5a → 5a, 5b 相對順序反轉
交換操作直接導致相等元素相對位置改變，無法通過修改比較條件修復（因交換對象非相鄰）。
五、改進變體：堆排序與樹選擇排序
| 變體 | 核心改進 | 複雜度 | 穩定性 |
|---|
| 堆排序 | 最大堆維護最小元素 | O(N log N) | 不穩定 |
| 樹選擇排序 | 敗者樹/勝者樹並行比較 | O(N log N) | 可穩定 |
| 循環選擇排序 | 雙向同時選最小/最大 | O(N²)，常數減半 | 不穩定 |
堆排序是選擇排序的工業級昇華：以堆結構將「掃描尋找最小」從 O(N) 降為 O(log N)，總複雜度達到理論下界 O(N log N)。
六、實務應用場景
- 閃存/EEPROM 寫入受限系統：每次寫入消耗壽命，選擇排序最小化寫入
- 記憶體受限嵌入式：O(1) 空間、無遞迴、確定性執行時間
- 教學基石：理解「選擇→交換」模式，通往堆排序、優先佇列的必經之路
- 小規模資料：N < 20 時，常數因子極小，實測常快於快速排序
七、現代 C++ 標準庫視角
std::sort 不使用選擇排序，但 std::partial_sort、std::nth_element 內部常用堆選擇邏輯。std::priority_queue 底層即最大堆，本質是動態維護的選擇排序機制。
總結
選擇排序以固定比較、最小移動、無適應性三大特性，佔據「寫入成本極高、資料分佈未知、空間極受限」的獨特生態位。其演化形態——堆排序——更是實現 O(N log N) 原地排序的基石演算法。理解選擇排序，即掌握了「以空間換時間、以結構優化選擇」的演算法設計核心哲學。
- 上一篇文章： 經典排序算法系列三：交換排序——氣泡排序與快速排序的淵源
- 下一篇文章： C++ I/O 流格式控制全攻略：從 ios_base 到操縱子的完整指南
Copyright ©
程式碼之家 All Rights Reserved
