插入排序

• 直接插入：
  • 将第 $i$ 个元素插入到前面 $i-1$ 个已排好序的序列中。
  • 稳定。最坏 $O(n^2)$，最好 $O(n)$（已有序）。
• 希尔排序 (Shell Sort)：
  • 思想：缩小增量。先将序列按增量 $d$ 分组，组内直接插入；逐渐减小 $d$ 至 1。
  • 不稳定。适合初期无序的数据。