插入排序法是一種基於比較的排序演算法。它透過構建一個已排序的序列，然後逐個將未排序的元素插入到已排序序列的適當位置，直到整個序列有序為止。
| 項目 | 複雜度 | 說明 |
|---|---|---|
| 最壞時間複雜度 | O(n²) | 陣列完全反向排序時 |
| 平均時間複雜度 | O(n²) | 隨機排序的情況 |
| 最佳時間複雜度 | O(n) | 陣列已排序時 |
| 空間複雜度 | O(1) | 只需常數大小的額外空間 |
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const key = arr[i];
let j = i - 1;
// 在已排序的部分中找到正確位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 將 key 插入到正確位置
arr[j + 1] = key;
}
return arr;
}