插入排序核心邏輯：將陣列分為「已排序區間」與「未排序區間」。每次從未排序區取出首元素，在已排序區中從右向左掃描，找到合適位置插入，並將後續元素右移。
時間複雜度：O(n²)（最好 O(n)、最壞 O(n²)、平均 O(n²)）
空間複雜度：O(1) 原地排序
穩定性：穩定（相等元素相對順序不變）
#include
void swap(int *a, int *b) {
int tmp = *a; *a = *b; *b = tmp;
}
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
// 將 arr[i] 插入到 arr[0..i-1] 中
for (int j = i; j > 0 && arr[j] < arr[j-1]; j--)
swap(&arr[j], &arr[j-1]);
// 或者用哨兵優化：先保存 key，後移元素，最後放入
}
}
int main() {
int data[] = {4, 7, 2, 6, 5, 9, 3, 8};
int n = sizeof(data) / sizeof(data[0]);
insertion_sort(data, n);
for (int i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
return 0;
} void insertion_sort_opt(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 後移大於 key 的元素
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key; // 插入
}
}優化版將「交換」改為「後移+單次賦值」，減少寫入內存次數，實際效能顯著提升。
n < 50）O(n)）| 算法 | 平均時間 | 最好 | 最壞 | 空間 | 穩定 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | ✓ |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | ✓ |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | ✗ |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ |
| 歸併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ |
