01先从一个问题出发
手里已经排好几张牌，新摸一张，不必把所有牌重新排列。
一个具体的例子
[2, 5, 3]：保存 3，把 5 右移，再把 3 放入空位，得到 [2, 3, 5]。
02最直接的办法，为什么慢？
每加入一个元素，就重新冒泡排序整个前缀。
暴力 · O(n³)
反复排序忽略了已有序的部分。
03一步步，推导出优化思路
1
发现可以复用的信息
前缀已排序时，新元素只需要寻找一个插入点。
2
建立可维护的状态
先保存 key，把所有大于 key 的前缀元素右移。
3
消除重复工作
空位出现后写入 key，有序前缀扩展一个元素。
贯穿算法的不变量
第 i 轮开始前，a[0:i] 已有序。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Insertion Sort交互演示
STEP 01 / 4735
018
152
227
343
412
560
631
7当前处理已处理 / 已确定未处理
01
从左到右观察数组。橙色表示当前比较，绿色表示已确定的位置。
insertion_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
逆序输入下每个元素最多向前走 i 步，总和为 O(n²)。近乎有序时很快；有序输入为 O(n)。
辅助空间
原地版本仅保存 key 和下标。教学函数复制输入，额外复制占 O(n)。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
保存 key
移动前必须保存原值，否则会被右移覆盖。
02
有序前缀不是最终位置
未来更小元素仍可能插到前面。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01最适合插入排序的输入？
02右移前为什么保存 key？
03稳定性需要什么条件？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。