排序

插入排序

插入排序会维护一个左侧有序区间。每次拿到右边的新元素，就不断和左边元素比较，把它向左移动，直到插入到正确位置。

如果数组本来接近有序，插入排序会很快；这也是它在小数组或局部有序数据里很常用的原因。

复杂度

  • 时间：最坏 O(n²)，最好 O(n)（已经有序时几乎只检查一遍）
  • 空间：O(1)，原地排序
  • 稳定性：相等元素不会互换位置，是稳定排序

在动画里看什么

  • 绿色：当前已经有序的前缀
  • 紫色：正在向左插入的元素
  • 蓝色：正在比较的相邻元素
  • 红色：元素向左移动时发生的交换