選擇排序演算法 C++ 實作與資料移動優勢分析

選擇排序以「最少交換次數」著稱，適合資料移動成本極高（如大型結構體、Flash 記憶體）的場景。本文提供標準實作、複雜度分析與適用場景對比。

核心邏輯

1. 從未排序區間找出最小值索引 min。
2. 將 min 與未排序區間首位 i 交換。
3. 重複直到整個陣列有序。

C++ 實作

#include <iostream>
using namespace std;

void SelectSort(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < len; ++j)
            if (arr[j] < arr[min]) min = j;
        if (min != i) swap(arr[i], arr[min]);
    }
}

int main() {
    int arr[] = {2, 4, 1, 0, 8, 4, 8, 9, 20, 7};
    SelectSort(arr, 10);
    for (int v : arr) cout << v << ' ';  // 0 1 2 4 4 7 8 8 9 20
}

複雜度與特性

優勢場景

• 記憶體寫入昂貴（EEPROM、Flash、大型物件陣列）。
• 交換操作極其耗時（需深拷貝、序列化、磁碟 I/O）。
• 教學示範「選擇-交換」基本邏輯。

劣勢與替代

• 一般隨機存取記憶體中，O(N²) 比較次數遠大於快速排序/歸併排序。
• 若需穩定排序，改用插入排序或歸併排序。
• 小規模資料（N < 50）插入排序常更快（常數因子小）。

總結

選擇排序雖非通用高效排序，但其「最小化寫入」特性在特定硬體/資料結構下具不可替代價值。理解各排序演算權衡，才能根據實際約束條件做最優選擇。