選擇排序：原理、實現與優化細節

算法思想

選擇排序每輪在未排序區間找出最小元素，與區間首元素交換。與冒泡排序不同，它每輪僅交換一次，減少寫入操作。

步驟演示

初始：2, 1, 5, 4, 9

1. 第 1 輪：最小 1 ↔ 2 → 1, 2, 5, 4, 9
2. 第 2 輪：最小 2 已在首 → 1, 2, 5, 4, 9
3. 第 3 輪：最小 4 ↔ 5 → 1, 2, 4, 5, 9
4. 第 4 輪：最小 5 已在首 → 1, 2, 4, 5, 9

代碼實現

void select_sort(int array[], int length) {
    if (NULL == array || length <= 1) return;

    for (int outer = 0; outer < length - 1; ++outer) {
        int min_idx = outer;

        // 在 [outer+1, length) 尋找最小值索引
        for (int inner = outer + 1; inner < length; ++inner) {
            if (array[inner] < array[min_idx])
                min_idx = inner;
        }

        // 若最小值不在首位，交換
        if (min_idx != outer) {
            int tmp = array[outer];
            array[outer] = array[min_idx];
            array[min_idx] = tmp;
        }
    }
}

複雜度分析

測試與驗證

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

void test() {
    int data[] = {2, 1, 5, 4, 9};
    int size = sizeof(data) / sizeof(int);

    printf("Before: "); print_array(data, size);
    select_sort(data, size);
    printf("After : "); print_array(data, size);
    // 輸出：1 2 4 5 9
}

優化與變體

• 雙向選擇排序：每輪同時找最小與最大，放到兩端，輪數減半（但比較次數不變）。
• 堆排序：用堆結構優化「找最小」至 O(log n)，整體達 O(n log n)。

總結

選擇排序雖屬 O(n²)，但交換次數極少，適合「寫入成本高」（如 Flash 記憶體）的場景。理解其「選最小、換到首」的核心邏輯，是掌握更高級排序算法的基石。