第二屏：课堂 insertionSort 代码（Java）
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
第三屏：插入排序原理（通俗版）
把数组看成两部分：左边“已经有序”，右边“还没处理”。每一轮都从右边拿一个元素插入左边。
- 第 1 行：循环变量 i 从 1 开始，表示“要插入的元素下标”。
- 第 2 行：key = a[i]，先把要插入的值保存下来。
- 第 3~6 行：从右往左找插入位置，遇到比 key 大的元素就右移一格。
- 第 7 行：把 key 放进空出来的位置，当前轮结束。
第 1 步：默认第 1 个元素有序
下标 0 先作为有序区间。
第 2 步：取出 key
每轮拿一个新元素，准备插入左侧有序区间。
第 3 步：右移大元素
只要左侧元素比 key 大，就向右挪一位。
第 4 步：key 落位
把 key 填到最终位置，有序区间扩大 1 格。
一句话记忆：取 key → 向左比较 → 大元素右移 → key 插入空位。
第四屏：插入排序的特点（重点）
稳定排序
相等元素不会跨越彼此前后顺序，适合多关键字排序。
原地排序，空间 O(1)
只用常数额外变量（key、j），内存开销很小。
时间复杂度有“自适应性”
最好 O(n)（近乎有序），平均/最坏 O(n²)。
适合小规模或近乎有序数据
数据规模不大时实现简单、常数开销低。
结论：插入排序最大的价值是“简单 + 稳定 + 近乎有序时很快”。
第六屏：最终结果 + 记忆要点
最终有序数组
3 条记忆要点
- 要点 1：每轮结束后，区间 [0..i] 一定有序。
- 要点 2：真正“动”的是大元素右移，key 最后一次性落位。
- 要点 3：数组越接近有序，插入排序越快。