什麼是選擇排序？
選擇排序是一種簡單直觀的排序算法：每輪在未排序區間中選出最小（或最大）元素，與未排序區間首位元素交換，逐步擴大已排序區間。
算法核心思想
- 將數組劃分為已排序區間（左側）和未排序區間（右側）
- 第
i 輪（從 0 開始），在 [i, n-1] 中找到最小元素下標 minIndex
- 若
minIndex != i，交換 a[i] 和 a[minIndex]
- 共需
n-1 輪，最後一個元素自然就位
逐輪演示（以 3 2 4 1 為例，升序）
| 輪次 | 未排序區間 | 最小值位置 | 交換操作 | 結果 |
|---|
| 1 | [3, 2, 4, 1] | 下標 3 (值 1) | 交換 a[0] 和 a[3] | [1, 2, 4, 3] |
| 2 | [2, 4, 3] | 下標 1 (值 2) | 無需交換 | [1, 2, 4, 3] |
| 3 | [4, 3] | 下標 3 (值 3) | 交換 a[2] 和 a[3] | [1, 2, 3, 4] |
完整 C 語言代碼實現
#include <stdio.h>
#include <stdlib.h>
#define N 8
void selectSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) { // n-1 輪選擇
int minIndex = i; // 假設當前位置最小
for (int j = i + 1; j < n; j++) { // 遍歷未排序區間
if (a[j] < a[minIndex])
minIndex = j; // 更新最小值下標
}
if (i != minIndex) { // 需要交換時才操作
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
int main() {
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
selectSort(num, N);
printf("排序結果：\n");
for (int i = 0; i < N; i++) printf("%d ", num[i]);
printf("\n");
return 0;
}
運行結果
排序結果：11 19 25 38 44 78 89 96
算法特性分析
| 特性 | 說明 |
|---|
| 時間複雜度 | 最好/平均/最壞均為 O(n²) |
| 空間複雜度 | O(1)，原地排序 |
| 穩定性 | 不穩定 |
| 交換次數 | 最多 n-1 次，最少 0 次 |
為什麼選擇排序不穩定？
例：序列 [5, 8, 5, 2, 9]，第一輪選最小值 2（下標 3），與第一個 5（下標 0）交換 → [2, 8, 5, 5, 9]。兩個 5 的相對順序被打亂（原先第一個 5 在前，交換後第二個 5 在前）。
選擇排序 vs 插入排序 vs 冒泡排序
| 算法 | 時間複雜度 | 穩定性 | 交換/移動次數 | 適用場景 |
|---|
| 選擇排序 | O(n²) | 不穩定 | 交換極少 (≤n) | 交換成本高、數據量小 |
| 插入排序 | O(n²) | 穩定 | 移動較多 | 近乎有序、需穩定 |
| 冒泡排序 | O(n²) | 穩定 | 交換較多 | 教學、極小數據 |
適用場景
- 數據量小（n < 100）
- 內存寫入成本極高（如 Flash 存儲），選擇排序交換次數最少
- 不要求穩定性
- 教學演示選擇策略
