插入排序是一種簡單直觀的排序算法，其工作原理類似於整理撲克牌：將未排序區間的元素逐個「插入」到已排序區間的適當位置，保持已排序區間始終有序。
| 輪次 | 已排序區間 | 待插入元素 | 操作過程 | 結果 |
|---|---|---|---|---|
| 1 | [3] | 2 | 2<3，插入位置 0，3 右移 | [2, 3] |
| 2 | [2, 3] | 4 | 4>3，直接插入末尾 | [2, 3, 4] |
| 3 | [2, 3, 4] | 1 | 1<2，插入位置 0，全部右移 | [1, 2, 3, 4] |
#include <stdio.h>
#include <stdlib.h>
#define N 8
void insertSort(int a[], int n) {
for (int i = 1; i < n; i++) { // 共 n-1 輪插入
int j = 0;
// 找到插入位置 j（第一個大於 a[i] 的位置）
while (j < i && a[j] < a[i]) j++;
if (i != j) { // 需要插入時才移動元素
int temp = a[i];
for (int k = i; k > j; k--) // 元素右移
a[k] = a[k - 1];
a[j] = temp; // 插入目標元素
}
}
}
int main() {
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
insertSort(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(n²) |
| 空間複雜度 | O(1)，原地排序 |
| 穩定性 | 穩定（相等元素相對順序不變） |
| 適應性 | 對近乎有序數據極快 |
比較時條件為 a[j] < a[i]（嚴格小於），遇到相等元素不移動，直接插入到相等元素後面，保持原有相對順序。
查找插入位置時可用二分查找替代線性查找，將比較次數從 O(n) 降為 O(log n)，但元素移動次數仍為 O(n²)，整體複雜度不變，適合比較操作昂貴的場景。
