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

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

題目需求

對 10 個整數由小到大進行選擇排序。
輸入範例：4 85 3 234 45 345 345 122 30 12
輸出範例：3 4 12 30 45 85 122 234 345 345

演算法思想

選擇排序每輪從未排序區間選出最小元素，與區間首元素交換；或選出最大元素放到區間尾部。本質是「選極值、換位置」，與冒泡排序的「相鄰比較、逐步冒泡」截然不同。

程式碼實作

#include <stdio.h>

void SelectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) {
            int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp;
        }
    }
}

int main() {
    int a[10];
    for (int i = 0; i < 10; ++i) scanf("%d", &a[i]);
    SelectionSort(a, 10);
    for (int i = 0; i < 10; ++i) printf("%d ", a[i]);
    return 0;
}

執行結果示意

複雜度分析

• 時間：O(n²) —— 無論輸入分佈，比較次數固定為 n(n-1)/2
• 空間：O(1) —— 原地排序
• 穩定性：不穩定（交換可能改變相等元素相對順序）

關鍵區別提醒

❌ 冒泡排序：相鄰比較、大元素逐步後移
✅ 選擇排序：全區間掃描極值、單次交換到位
面試常考兩者差異，請務必釐清。