選擇排序法實作與分析：從冒泡排序到高效排序演進

程式碼審視

原標題「冒泡排序改良」，實際程式碼實作為選擇排序：每輪掃描未排序區間最小值，與首位交換。

完整可執行程式

#include <stdio.h>
#include <stdlib.h>

#define LEN 10

int main(void) {
    int array[LEN];
    int i, j, min, tmp;

    printf("請輸入 %d 個整數：", LEN);
    for (i = 0; i < LEN; ++i) scanf("%d", &array[i]);

    printf("原始資料：");
    for (i = 0; i < LEN; ++i) printf("%d ", array[i]);
    putchar('\n');

    // 選擇排序
    for (i = 0; i < LEN - 1; ++i) {
        min = i;
        for (j = i + 1; j < LEN; ++j)
            if (array[min] > array[j]) min = j;

        if (min != i) {
            tmp = array[min];
            array[min] = array[i];
            array[i] = tmp;
        }
    }

    printf("排序結果：");
    for (i = 0; i < LEN; ++i) printf("%d ", array[i]);
    putchar('\n');
    return 0;
}

複雜度分析

優化方向

• 小規模資料（n < 50）選擇排序常因低常數因子優於快排
• 大規模資料建議 qsort / std::sort (Introsort)
• 近乎有序資料：插入排序 O(n)

圖示說明