演算法實作筆記：選擇排序原理、C 語言實作與效能分析

選擇排序核心思想

選擇排序是一種簡單直觀的原地比較排序。它將陣列劃分為「已排序區」（左側）與「未排序區」（右側）。每一輪從未排序區中找出最小（或最大）元素，將其與未排序區的第一個元素交換，從而擴展已排序區邊界。與冒泡排序「相鄰交換」不同，選擇排序每輪最多只交換一次，減少寫入操作。

執行過程示例

初始陣列：[2, 1, 5, 4, 9]

C 語言標準實作

void selection_sort(int arr[], int len) {
    if (!arr || len <= 1) return;

    for (int i = 0; i < len - 1; ++i) {
        int min_idx = i;
        // 在 [i+1, len-1] 尋找最小值索引
        for (int j = i + 1; j < len; ++j) {
            if (arr[j] < arr[min_idx]) min_idx = j;
        }
        // 若最小值不在當前位置，交換
        if (min_idx != i) {
            int tmp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = tmp;
        }
    }
}

測試驅動

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; ++i) printf("%d ", arr[i]);
    putchar('\n');
}

void test_selection_sort(void) {
    int data[] = {2, 1, 5, 4, 9};
    int n = sizeof(data) / sizeof(data[0]);
    selection_sort(data, n);
    print_array(data, n);  // 輸出：1 2 4 5 9
}

複雜度分析

優缺點總結

優點

• 實作簡單，程式碼極短，適合教學與嵌入式資源受限環境。
• 交換次數最少（≤ n-1），對「寫入成本高」的存儲介面（如 EEPROM、Flash）較友好。
• 無遞迴、無額外記憶體，堆疊安全。

缺點

• 時間複雜度固定 O(n²)，不適合大規模資料。
• 不穩定，無法直接用於多關鍵字排序（需改用索引間接排序）。
• 無法利用資料「部分有序」特性優化（不像插入排序最佳 O(n)）。

常見變體與優化

1. 雙向選擇排序：每輪同時找最小值放左端、最大值放右端，輪數減半（但比較次數不減）。
2. 堆排序：以二元堆優化「尋找最小值」為 O(log n)，整體達 O(n log n)，是選擇排序的進階形態。
3. 索引間接排序：不移動大物件，只排序索引陣列，最後按索引重組，提升大物件排序效能。

總結

選擇排序雖非高效排序首選，但其「最小交換次數、原地、簡單」的特性使其在特定場景（小規模資料、寫入昂貴、教學示範）仍具價值。理解其「選擇+交換」模板，有助於進一步掌握堆排序、循環選擇排序等進階演算法。