插入排序

从第二位开始与前面位比较，小于/大于前面的值，就放前边去

• 效率相比冒泡、选择排序更好；chrome V8排序数小于22个使用插入排序，大于22使用的是快速排序

• 时间复杂度最优O(n) 最差O(n^2) 空间复杂度O(n) 是否稳定：取决于是否判断min !== i

function insertionSort(arr) {
  let len = arr.length
  // 外层循环控制对比目标
  for (let i = 1; i < len; i++) {
    let tmp = arr[i] // 目标值
    let j = i
    // 前一个值大于目标值(升序)
    while (j > 0 && arr[j - 1] > tmp) {
      arr[j] = arr[j - 1] // 赋值前一个,(相当于把arr[j-1]往后一个，准备为新值腾出位置)
      j-- // 递减逐个与目标值比较
    }
    arr[j] = tmp // 插到合适的位置
  }
  return arr
}

let res = insertionSort([6, 7, 4, 2, 3, 1])
console.log(res)

参考