C語言選擇排序算法詳解與實現

選擇排序 是最直觀的排序算法之一：每一輪從未排序區間找出最小元素，放到已排序區間末尾。雖然時間複雜度固定為 O(n²)，但交換次數最少（最多 n-1 次），在數據移動開銷大時有一定優勢。

算法步驟

1. 從索引 0 開始，假設當前位置為最小值位置 minIdx。
2. 在剩餘未排序區間（i+1 到 n-1）中遍歷，找到真正最小值的索引。
3. 若 minIdx != i，交換兩者位置。
4. 重複 n-1 輪，完成排序。

代碼實現

#include 
#include 
#include 

#define N 10

int main() {
    int a[N], i, j, k, t;

    srand((unsigned)time(NULL));
    printf("隨機產生 10 個 100 以內的數:\n");
    for (i = 0; i < N; i++) {
        a[i] = rand() % 100;
        printf("%d ", a[i]);
    }
    printf("\n");

    // 選擇排序核心邏輯
    for (i = 0; i < N-1; i++) {
        k = i;  // 假設當前位置最小
        for (j = i+1; j < N; j++) {
            if (a[j] < a[k]) {
                k = j;  // 記錄最小值索引
            }
        }
        if (k != i) {  // 需要交換
            t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
    }

    printf("排序後輸出:\n");
    for (i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

運行結果示例

隨機產生 10 個 100 以內的數:
45 12 89 33 7 56 21 98 4 67
排序後輸出:
4 7 12 21 33 45 56 67 89 98

算法特性分析

優化思路

• 雙向選擇排序：每輪同時找最小值放前端、最大值放後端，輪數減半。
• 堆排序：利用堆結構優化「找最小值」過程，將 O(n) 降為 O(log n)，整體達到 O(n log n)。

總結

選擇排序邏輯清晰、代碼簡短、交換次數最少，是教學與小規模數據排序的優秀選擇。理解其「選最小、換到位」的核心思想，有助於掌握堆排序等進階算法。實際工程中，對性能敏感場景請優先考慮快速排序、歸並排序或系統庫函數 qsort。