insertion-sort

插入排序

数据量小的时候还可以用一下。

• 稳定性

  稳定（人为控制插入位置）

• 复杂度

  • 时间复杂度

    O(n) ~ O(n^2)

    • 最好情况

      数组有序

    • 最差情况

      数组逆序

  • 空间复杂度

    O(1)

    根本就不需要额外空间

• 原理

  从第一个位置开始遍历，把当前遇到的数字插入到前面对应位置上（然后其他数字后移）。

• 优化方法

  位置寻找逻辑改为二分查找（实际上也快不了多少，毕竟位移是整体平移的），仅限于比较操作耗时比较高的场景。