數據結構：C語言實現選擇排序（Selection Sort）完整教學

編輯：關於C語言

選擇排序核心思想

選擇排序是一種簡單直觀的排序算法：

在未排序序列中找到最小（大）元素
將其放到已排序序列的末尾
重複直到所有元素排序完成

時間複雜度：O(n²) | 空間複雜度：O(1) | 不穩定排序

標準實現代碼

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

#define MAXN 100

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        // 在未排序區間 [i+1, n-1] 尋找最小值索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 若最小值不在當前位置，交換
        if (min_idx != i) {
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

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

int main() {
    int arr[] = {44, 33, 55, 999, 42};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: "); print_array(arr, n);
    selection_sort(arr, n);
    printf("排序後: "); print_array(arr, n);

    return 0;
}

執行流程圖解（以 {44, 33, 55, 999, 42} 為例）

輪次	未排序區間	最小值	交換動作	數組狀態
1	[44, 33, 55, 999, 42]	33	swap(44, 33)	[33, 44, 55, 999, 42]
2	[44, 55, 999, 42]	42	swap(44, 42)	[33, 42, 55, 999, 44]
3	[55, 999, 44]	44	swap(55, 44)	[33, 42, 44, 999, 55]
4	[999, 55]	55	swap(999, 55)	[33, 42, 44, 55, 999]

關鍵點總結

外層循環 n-1 次：最後一個元素自然有序
內層尋找最小索引：而非最小值本身，便於交換
僅當 min_idx != i 時交換：減少不必要的賦值操作
原地排序：無額外空間開銷

優化變體：雙向選擇排序

同時選最小值放前、最大值放後，將外層循環次數減半：

void selection_sort_bidirectional(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        int min_idx = left, max_idx = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min_idx]) min_idx = i;
            if (arr[i] > arr[max_idx]) max_idx = i;
        }
        // 處理 min/max 重疊等邊界情況...
        // 交換邏輯略
        left++; right--;
    }
}

適用場景

小規模數據（n < 50）
記憶體寫入代價極高時（交換次數最少，最多 n-1 次）
教學演示排序基本原理

對比：選擇 vs 冒泡 vs 插入

| 算法 | 平均時間 | 最好情況 | 穩定性 | 交換次數 | |------|----------|----------|--------|----------| | 選擇排序 | O(n²) | O(n²) | 不穩定 | O(n) | | 冒泡排序 | O(n²) | O(n) | 穩定 | O(n²) | | 插入排序 | O(n²) | O(n) | 穩定 | O(n²) |

選擇排序最大優勢在於交換次數最少，適合「寫入代價高、讀取代價低」的存儲介質（如 EEPROM、Flash）。