插入排序

(图片来自 插入排序 - 十大经典排序算法

思路

插入排序很像打扑克牌时候的排序方式,每发一张牌,我们就将这张牌插入手中已经排好序的牌,因此得名。其算法步骤如下:

  1. 将第 1 个待排序的元素看做一个有序序列,把第 2 个元素到最后一个元素当成是未排序序列。
  2. 遍历所有的未排序序列,每次遍历都将它插入到有序序列的正确位置。

分析

  • 平均时间复杂度显然为 $O(n^2)$。
  • 最好的情况就是数组已排好序,在遍历时每个结点只需要 2 次比较,复杂度为 $O(n)$。
  • 最坏的情况为该数组是反序,此时复杂度已经拉满,为 $O(n^2)$。
  • 空间复杂度为 $O(1)$,不需要额外空间。
  • 算法稳定,在对比的时候只有当左数大于右数时才交换,相等时不交换。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。