插入排序

一句话理解

插入排序：把当前元素插入前面已经有序的序列。

为什么要学

接近有序时很快，是 sort 处理小数组的手段之一。

讲解

从左到右，把 a[i] 向前挪到正确位置。最坏 O(n²)，最好接近 O(n)。

例子

for (int i = 1; i < n; i++) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
    a[j + 1] = x;
}

像整理扑克牌。

常见错误

• while 条件 j>=0 忘了，越界。
• 覆盖 a[i] 前没存到 x。