C 語言排序演算法：選擇排序原理與完整實現

什麼是選擇排序？

選擇排序 是一種簡單直觀的原地比較排序演算法。核心思想：每一輪從未排序區間找到最小 (或最大) 元素，放到已排序區間的末尾。

演算法流程 (升序)

1. 初始：整個陣列為「未排序區」。
2. 第 i 輪 (i = 0 到 n-2)：
   1. 假設未排序區第一個元素 arr[i] 為最小值，記錄索引 min_idx = i。
   2. 遍歷未排序區剩餘元素 (j = i+1 到 n-1)，若發現 arr[j] < arr[min_idx]，更新 min_idx = j。
   3. 遍歷結束後，若 min_idx != i，交換 arr[i] 與 arr[min_idx]。
3. 重複直到未排序區只剩一個元素。

完整可運行程式碼 (修正原答案邏輯錯誤)

#include <stdio.h>

#define SIZE 10

void selection_sort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {         // 輪數：只需 n-1 輪
        min_idx = i;                      // 假設當前為最小
        for (j = i + 1; j < n; j++) {     // 掃描未排序區
            if (arr[j] < arr[min_idx]) {  // 找到更小
                min_idx = j;              // 更新最小值索引
            }
        }
        if (min_idx != i) {               // 需要交換
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

void print_arr(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%4d", arr[i]);
    printf("\n");
}

int main() {
    int arr[SIZE] = {32, 62, 12, 96, 34, 67, 12, 36, 38, 73};
    printf("原始陣列: "); print_arr(arr, SIZE);
    selection_sort(arr, SIZE);
    printf("排序後:   "); print_arr(arr, SIZE);
    return 0;
}

複雜度分析

優化變體：雙向選擇排序

每輪同時找最小值放左端、最大值放右端，輪數減半 (但比較次數不變)。適合「交換成本極高」的場景 (如大型結構體陣列)。

何時使用選擇排序？

• 資料量極小 (n < 50)。
• 記憶體寫入極其昂貴 (如 EEPROM/Flash 寫入)，因交換次數最少。
• 教學演示、嵌入式系統資源極受限環境。

生產環境大數據排序請使用 qsort (快速排序) 或 C++ std::sort (內省排序)，平均 O(n log n)。