插入排序在做什么（摸牌类比）
想象你在打牌，左手已经抓了一手排好序的牌，右手从桌上摸起一张新牌。你的任务是把这张新牌插入到左手牌中正确的位置，使得左手依然有序。这就是插入排序的核心思想：将数组视为两部分——左边是已排序区，右边是未排序区，每次从右边取第一个元素，插入到左边合适的位置。
一次插入的流程：右移腾位再放入
假设已排序区有若干元素，现在要插入一个新元素。流程是：
- 先记住新元素的值；
- 从已排序区的最后一个元素开始，依次与它比较，如果比它大，就把那个元素向右移动一位，腾出一个空位；
- 直到找到第一个不大于它的元素，或者到达最左边，然后把新元素放入空位。
最好/最坏复杂度（为什么近乎有序时 O(n)）
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好（已有序） | O(n) | 每次插入只需比较一次（新元素比已排序区最后一个大），无需移动，直接放在末尾。 |
| 最坏（逆序） | O(n²) | 每次插入都要比较和移动所有已排序元素，总比较和移动次数约为 n²/2。 |
| 平均 | O(n²) | 随机顺序下，平均比较和移动次数约为 n²/4。 |
当数组近乎有序时，大部分元素只需少量比较和移动，因此复杂度接近 O(n)。这是插入排序的重要特性。
稳定性
稳定。插入排序在插入时，如果遇到相等元素，通常将新元素放在相等元素之后（即不越过相等元素），因此保持了相等元素的原始相对顺序。这对于需要稳定排序的场景很重要。
适用场景：小数组、近乎有序
插入排序适合小规模数据（如几十个元素），因为其常数因子小，实现简单。也特别适合近乎有序的数组，此时效率接近线性。许多高级排序（如快速排序）在递归到小数组时会切换到插入排序以提升性能。