插入排序

为什么不像选择排序那样扫全局？因为左边已经有序了，新牌只要和左边从右往左挨个比，遇到第一个不比它大的就停——逆序时最慢要比到头（O(n²)），但近乎有序时几乎一比就停（O(n)）。

每插入完第 i 个数，前缀 0..i 一定有序。插入靠的是"把左边比它大的整体右移一格腾出空位"，而不是交换——右移比交换省一次赋值，还保持稳定。

5 是已排序起点：先把第一个数 5 看作已排序区（绿色）。从下标 1 开始，把右边的数一张张往左插。

取出 2 · 准备往左插：轮到下标 1 的 2（橙色）。把它取出暂存，下标 1 这格视作空位，接下来和左边已排序的数从右往左比。

比较 · 5 > 2？：和左边下标 0 的 5 比：5 大于 2，它得给 2 让位，右移一格。

右移 · 5 → 下标 1：把 5 右移到下标 1（不是交换，只是复制一格）。空位左移到下标 0，cur=2 继续往左比。

落位 · 2 放进下标 0：左边到头（j=-1），没有更多牌可比，把暂存的 2 放进腾出的下标 0。前缀 0..1 变成 [2, 5]，依旧有序。

取出 4 · 准备往左插：轮到下标 2 的 4（橙色）。把它取出暂存，下标 2 这格视作空位，接下来和左边已排序的数从右往左比。

比较 · 5 > 4？：和左边下标 1 的 5 比：5 大于 4，它得给 4 让位，右移一格。

右移 · 5 → 下标 2：把 5 右移到下标 2（不是交换，只是复制一格）。空位左移到下标 1，cur=4 继续往左比。

落位 · 4 放进下标 1：下标 0 的 2 不大于 4，循环停下，把暂存的 4 放进腾出的下标 1。前缀 0..2 变成 [2, 4, 5]，依旧有序。

取出 1 · 准备往左插：轮到下标 3 的 1（橙色）。把它取出暂存，下标 3 这格视作空位，接下来和左边已排序的数从右往左比。

比较 · 5 > 1？：和左边下标 2 的 5 比：5 大于 1，它得给 1 让位，右移一格。

右移 · 5 → 下标 3：把 5 右移到下标 3（不是交换，只是复制一格）。空位左移到下标 2，cur=1 继续往左比。

比较 · 4 > 1？：和左边下标 1 的 4 比：4 大于 1，它得给 1 让位，右移一格。

右移 · 4 → 下标 2：把 4 右移到下标 2（不是交换，只是复制一格）。空位左移到下标 1，cur=1 继续往左比。

比较 · 2 > 1？：和左边下标 0 的 2 比：2 大于 1，它得给 1 让位，右移一格。

右移 · 2 → 下标 1：把 2 右移到下标 1（不是交换，只是复制一格）。空位左移到下标 0，cur=1 继续往左比。

落位 · 1 放进下标 0：左边到头（j=-1），没有更多牌可比，把暂存的 1 放进腾出的下标 0。前缀 0..3 变成 [1, 2, 4, 5]，依旧有序。

取出 3 · 准备往左插：轮到下标 4 的 3（橙色）。把它取出暂存，下标 4 这格视作空位，接下来和左边已排序的数从右往左比。

比较 · 5 > 3？：和左边下标 3 的 5 比：5 大于 3，它得给 3 让位，右移一格。

右移 · 5 → 下标 4：把 5 右移到下标 4（不是交换，只是复制一格）。空位左移到下标 3，cur=3 继续往左比。

比较 · 4 > 3？：和左边下标 2 的 4 比：4 大于 3，它得给 3 让位，右移一格。

右移 · 4 → 下标 3：把 4 右移到下标 3（不是交换，只是复制一格）。空位左移到下标 2，cur=3 继续往左比。

落位 · 3 放进下标 2：下标 1 的 2 不大于 3，循环停下，把暂存的 3 放进腾出的下标 2。前缀 0..4 变成 [1, 2, 3, 4, 5]，依旧有序。

全部插完 · 数组有序：五张牌全部插完，前缀铺满整个数组，[1, 2, 3, 4, 5] 完全有序。这就是插入排序的全过程。

三个高频追问：右移 vs 交换、自适应优势、以及越界判断为什么要放在前面。