🔄 選擇排序法完整教學
程式碼、原理與運作演示
📌 基本概念
選擇排序法（Selection Sort）是一種簡單直觀的排序演算法。其基本思想是：每一輪從尚未排序的元素中選出最小值，放到已排序序列的末端。重複此步驟直到所有元素排序完成。
這個演算法通過不斷選擇最小元素來建構排序序列，適合用於理解排序的基本概念，但在實際應用中性能不如其他排序演算法。
⚙️ 詳細運作原理
演算法步驟：
1
外層迴圈：走訪整個數列 n-1 次（n 是數列長度）
2
尋找最小值：在未排序區間中找到最小元素的索引
3
交換元素：將最小元素與未排序區間的第一個元素交換
4
縮小範圍：已排序區間擴大，未排序區間縮小
虛擬程式碼：
for i = 0 to n-2:
minIndex = i
for j = i+1 to n-1:
if arr[j] < arr[minIndex]:
minIndex = j
swap arr[i] and arr[minIndex]
📊 具體例子 - 排序 [5, 2, 8, 1, 9]
初始陣列： [5, 2, 8, 1, 9]
第 1 輪：
未排序區間: [5, 2, 8, 1, 9]
尋找最小值: 1 (索引 3)
交換 5 和 1 → [1, 2, 8, 5, 9]
1 已在正確位置
第 2 輪：
未排序區間: [2, 8, 5, 9]
尋找最小值: 2 (索引 1)
2 已在第一位，無需交換 → [1, 2, 8, 5, 9]
2 已在正確位置
第 3 輪：
未排序區間: [8, 5, 9]
尋找最小值: 5 (索引 3)
交換 8 和 5 → [1, 2, 5, 8, 9]
5 已在正確位置
第 4 輪：
未排序區間: [8, 9]
尋找最小值: 8 (索引 3)
8 已在第一位，無需交換 → [1, 2, 5, 8, 9]
數列已排序完成
💻 C語言完整程式碼
#include <stdio.h>
// 選擇排序函數
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
// 外層迴圈：走訪 n-1 次
for (i = 0; i < n-1; i++) {
// 假設當前位置是最小值
minIndex = i;
// 內層迴圈：尋找未排序區間中的最小值
for (j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果找到更小的值，進行交換
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
// 主程式
int main() {
// 定義數組
int numbers[] = {5, 2, 8, 1, 9};
int n = sizeof(numbers)/sizeof(numbers[0]);
// 顯示原始陣列
printf("原始數列: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n\n");
// 執行選擇排序
selectionSort(numbers, n);
// 顯示排序後的陣列
printf("排序後的數列: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
程式輸出：
原始數列: 5 2 8 1 9
排序後的數列: 1 2 5 8 9
⏳ 時間與空間複雜度
| 最佳/平均/最壞時間複雜度 | O(n²) |
|---|
| 空間複雜度 | O(1) |
|---|
| 排序穩定性 | 不穩定 |
|---|
優點：
- 簡單易懂，適合教學
- 原地排序，空間需求低
- 交換次數少，最多 n-1 次
缺點：
✅ 優缺點分析
✓ 優點：
- 簡單易懂：演算法邏輯直觀，新手容易理解
- 原地排序：只需要常數級別的額外空間 O(1)
- 交換次數少：最多只進行 n-1 次交換
- 易於實現：程式碼簡潔，容易除錯
- 適合小資料集：當資料量很小時效能尚可
✗ 缺點：
- 效率低：平均時間複雜度為 O(n²)，不適合大型資料集
- 比較次數多：即使資料已大致排序，仍需進行大量比較
- 不穩定排序：相同值的元素相對順序可能改變
- 不適合實務應用：當數據量大時，效能顯著下降
🎮 互動可視化演示
請點擊「下一步」按鈕逐步觀察選擇排序的每一輪過程。不同顏色表示不同的狀態：
- 綠色：已排序區間
- 粉色：當前找到的最小值
- 藍色：正在比較的元素
🎯 應用場景
- 教育用途：學習排序演算法的基礎概念
- 小規模資料：當資料量很小（< 100 元素）時
- 記憶體受限：當記憶體空間非常有限時
- 演算法理解：理解選擇和交換的概念
- 簡單實現：當簡單易懂比效率更重要時
🔀 與其他排序算法的比較
| 演算法 |
時間複雜度
(平均) |
空間複雜度 |
穩定性 |
應用 |
| 氣泡排序 |
O(n²) |
O(1) |
✓ 穩定 |
教育用途 |
| 選擇排序 |
O(n²) |
O(1) |
✗ 不穩定 |
簡單場景 |
| 插入排序 |
O(n²) |
O(1) |
✓ 穩定 |
小規模資料 |
| 快速排序 |
O(n log n) |
O(log n) |
✗ 不穩定 |
一般應用 |
| 歸併排序 |
O(n log n) |
O(n) |
✓ 穩定 |
大型資料集 |
| 堆本排序 |
O(n log n) |
O(1) |
✗ 不穩定 |
需要保證效率 |
📝 總結
選擇排序法是學習排序演算法時的重要基礎，它清楚地演示了選擇和交換的基本概念。雖然在實務應用中因為效率問題而較少使用，但它對於理解演算法設計和複雜度分析仍然非常有價值。
當您需要排序小規模資料或進行教學演示時，選擇排序法是一個簡單且實用的選擇。但對於生產環境或大型資料集，應該選擇效率更高的演算法如快速排序或歸併排序。