插入一个数 · 考级冲刺

往一个有序数组的中间插入一个数，不能直接盖在某个位置上——那会把原来的元素冲掉。正确做法是：先把插入点及其后面的元素整体往后挪一格，腾出一个空位，再把新数放进去，长度加一。

关键是挪的方向要从后往前：

// 把 x 插到下标 pos，数组原长 n（保证 pos <= n）
for (int i = n; i > pos; i--)
    a[i] = a[i - 1];   // 从最后往前，逐个后移一格
a[pos] = x;            // 空位放入新数
n++;                   // 长度加一

为什么必须从后往前挪？因为后移是“把前一个复制到后一个”。如果从前往后做，会先用一个元素覆盖掉它后面还没挪走的元素，那个值就丢了，后面全被同一个数刷屏。从后往前挪，每次搬去的目标位置都是已经腾空（或已备份）的，才不会互相覆盖。

复杂度 $O (n)$ ：最坏要挪动几乎整个数组。所以在数组头部频繁插入很慢——这也是为什么“需要经常在中间插入”的场景，数组不是好选择。别忘了数组要预留足够空间，否则 a[n] 就越界了。