思路：插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”。
具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置。

为了更好的理解插入排序，可以看看插入排序的动画：https://visualgo.net/zh/sorting

插入排序里的几个关键点：

  • 当前元素前面的那个序列是有序的
  • “正确的位置”如何定义——所有在当前元素前面的数都不大于它，所有在当前元素后面的数都不小于它
  • 在有序序列里定位元素位置的时候，是从后往前定位的。只要发现一个比当前元素大的值，就需要为当前元素腾出一个新的坑位。

基于这个思路，我们来写代码：

  1. function insertSort(arr) {
  2.   // 缓存数组长度
  3.   const len = arr.length
  4.   // temp 用来保存当前需要插入的元素
  5.   let temp  
  6.   // i用于标识每次被插入的元素的索引
  7.   for(let i = 1;i < len; i++) {
  8.     // j用于帮助 temp 寻找自己应该有的定位
  9.     let j = i
  10.     temp = arr[i]  
  11.     // 判断 j 前面一个元素是否比 temp 大
  12.     while(j > 0 && arr[j-1] > temp) {
  13.       // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
  14.       arr[j] = arr[j-1]   
  15.       j--
  16.     }
  17.     // 循环让位，最后得到的 j 就是 temp 的正确索引
  18.     arr[j] = temp
  19.   }
  20.   return arr
  21. }

插入排序的时间复杂度

  • 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
  • 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)
  • 平均时间复杂度：O(n^2)