🔄 插入排序法完整教學
程式碼、原理與運作演示
📌 基本概念
插入排序法（Insertion Sort）是一種簡單的排序演算法。其基本思想是：將未排序的元素逐一插入到已排序序列的正確位置。類似於整理撲克牌，將每一張牌插入到已排序牌中的適當位置。
這個演算法適合用於理解排序的基本概念，尤其在資料已大致排序時效能良好，但在實際應用中對於大型資料集仍有改進空間。
⚙️ 詳細運作原理
演算法步驟：
1
初始化：將第一個元素視為已排序序列
2
取出元素：從第二個元素開始，取出下一個未排序元素
3
比較插入：與已排序序列從右向左比較，找到正確位置
4
移動元素：將大於取出元素的元素向右移動，為新元素騰出空間
虛擬程式碼：
for i = 1 to n-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = key
📊 具體例子 - 排序 [5, 2, 8, 1, 9]
初始陣列： [5, 2, 8, 1, 9]
第 1 輪：插入 2
取出 2，與已排序序列 [5] 比較
2 < 5，向右移動 5，插入 2 → [2, 5, 8, 1, 9]
2 已插入正確位置
第 2 輪：插入 8
取出 8，與已排序序列 [2, 5] 比較
8 > 5，無需移動，8 已在正確位置 → [2, 5, 8, 1, 9]
8 已插入正確位置
第 3 輪：插入 1
取出 1，與已排序序列 [2, 5, 8] 比較
1 < 8，向右移動 8；1 < 5，向右移動 5；1 < 2，向右移動 2
插入 1 → [1, 2, 5, 8, 9]
1 已插入正確位置
第 4 輪：插入 9
取出 9，與已排序序列 [1, 2, 5, 8] 比較
9 > 8，無需移動，9 已在正確位置 → [1, 2, 5, 8, 9]
數列已排序完成
💻 C語言完整程式碼
#include <stdio.h>
// 插入排序函數
void insertionSort(int arr[], int n) {
int i, j, key;
// 從第二個元素開始
for (i = 1; i < n; i++) {
key = arr[i]; // 取出當前元素
j = i - 1;
// 將大於 key 的元素向右移動
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 插入 key 到正確位置
arr[j + 1] = key;
}
}
// 主程式
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");
// 執行插入排序
insertionSort(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(n²) |
|---|
| 空間複雜度 | O(1) |
|---|
| 排序穩定性 | 穩定 |
|---|
優點：
- 簡單易懂，適合教學
- 原地排序，空間需求低
- 穩定排序
- 已排序或近排序資料時效率高
缺點：
- 效率低，平均/最壞情況下為 O(n²)
- 不適合大量資料
✅ 優缺點分析
✓ 優點：
- 簡單易懂：演算法邏輯直觀，新手容易理解
- 原地排序：只需要常數級別的額外空間 O(1)
- 穩定排序：相同值的元素相對順序不變
- 自適應：已排序或近似排序的陣列時間複雜度為 O(n)
- 線上排序：可以處理串流資料，隨時插入新元素
✗ 缺點：
- 效率低：平均時間複雜度為 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) |
✗ 不穩定 |
需要保證效率 |
📝 總結
插入排序法是學習排序演算法時的重要基礎，它清楚地演示了插入和比較的基本概念。雖然在實務應用中因為效率問題而較少使用，但它對於理解演算法設計和複雜度分析仍然非常有價值。
當您需要排序小規模或近似排序的資料，或是需要穩定排序時，插入排序法是一個簡單且實用的選擇。但對於生產環境或大型資料集，應該選擇效率更高的演算法如快速排序或歸併排序。