簡單選擇排序：減少交換次數的選擇策略

核心思想：選擇而非交換

冒泡排序透過頻繁交換相鄰元素將大值「冒泡」至末尾，交換次數多。簡單選擇排序改為每輪僅交換一次：在未排序區間掃描找出最小值索引，再與區間首位元素交換。此策略將交換次數從 O(n²) 降至 O(n)，適合「寫入成本高」（如 Flash 記憶體、EEPROM）的場景。

演算法流程

1. 外層迴圈 i = 0 ~ n-2，標記當前待確定位置。
2. 內層迴圈 j = i+1 ~ n-1，掃描未排序區間，記錄最小值索引 min。
3. 若 min != i，交換 arr[i] 與 arr[min]。
4. 重複直到 i = n-2，排序完成。

C 語言完整實現代碼

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

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void SelectSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min]) min = j;
        if (min != i) swap(arr, i, min);
    }
}

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

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：\n"); print(arr, n);
    SelectSort(arr, n);
    printf("排序後：\n"); print(arr, n);
    return 0;
}

效能特性分析

與冒泡排序對比

• 比較次數：相同，均為 n(n-1)/2。
• 交換/移動次數：選擇排序遠少於冒泡排序（冒泡最壞 O(n²) 次交換）。
• 適應性：冒泡排序對有序資料可優化至 O(n)；選擇排序無適應性，始終全量掃描。

總結

簡單選擇排序以「最少交換」為核心優勢，雖時間複雜度仍為 O(n²)，但在特定硬體約束下極具價值。理解其與冒泡、插入排序的差異，有助於根據資料特徵與硬體環境選擇最適合的基礎排序演算法。