我想知道这是为什么 –费曼

从有序序列的尾部开始，逐个与目标元素比较，如果大于该元素，该元素需要后移

核心是如何在有序序列里找到正确的插入位置
有点像打牌开始的时候整理手牌，每次都把新发的牌从最右侧的手牌一张张往左看，把新牌插入已经排好顺序的手牌里。

缓存目标元素，从有序序列尾部开始逐个比较，
如果当前序列的数字大于目标元素则把当前序列的数字后移到目标元素的位置上（目标元素的值已经缓存了，同时后移后当前序列数字的位置变为空），
继续逐个比较，如果目标元素大于当前序列数字，当前序列数字就后移
如果小于等于当前序列数字就把目标元素插入 上一次移动序列数字后的空位里

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function insertionSort(array) {
  for (let i = 0; i < array.lenth; i++) {
    let j = i
    let target = array[j]
    while (j > 0 && array[j - 1] > target) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = target
  }
  return array
}

复杂度 && 总结

插入排序不需要额外空间，是本地排序，相等元素是不会交换前后顺序，因而也是稳定排序，时间复杂度为 O(n^2)，适用于少量数据排序。相比冒泡排序和选择排序，插入排序的使用相对多一些。因为前两者是交换排序，本质上需要 3 次原子操作的。

我创建了一个集合 jest 可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
后续的文章将同步代码到这个项目下

使用 vscode 的读者可以安装拓展插件 jest，这个插件可以自动检测 test 文件自动运行，非常方便。

感谢老姚的文章 手写算法并记住它：插入排序