Insertion Sort
插入排序
排序入门时间 O(n²) / 近乎有序 O(n)空间 O(1)
把当前牌插入左手已经排好的序列。小数组或近乎有序时非常快。
动画
7
2
9
4
1
8
5
3
插入排序：把当前元素插入到左侧有序区。
1 / 32
- 已就位
- 默认
讲解
TimSort / IntroSort 处理短区间的底层；理解「有序区扩展」。
- 01左侧 [0, i) 有序，取出 a[i] 作为 key。
- 02把比 key 大的元素右移，给 key 腾位置。
- 03放入正确下标，有序区变为 [0, i]。
易错点
- 右移时从后往前，避免覆盖 key。
- 和选择排序不同：插入排序是稳定的。
代码
function insertionSort(a) {
for (let i = class="text-accent">1; i < a.length; i++) {
const key = a[i];
let j = i - class="text-accent">1;
while (j >= class="text-accent">0 && a[j] > key) {
a[j + class="text-accent">1] = a[j];
j--;
}
a[j + class="text-accent">1] = key;
}
return a;
}