数组排序算法 — 插入排序

对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？

本系列文章就尝试解决这个问题。

研读那些排序算法，细品它们的名字，其实都很贴切。

比如插入排序，所谓“插入”，实指把待排序元素插入到已排好的序列里。

上图演示了第4次遍历，此时元素1、3、5已经是有序序列，待排的元素是2，要把它插入到1和3之间。此时3和5都往后移动了一位。

可以看出该算法的核心是：如何在有序序列里找到正确的插入位置？

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

可以看出之所以先要缓存一下目标，是为了要把它的位置先空下来，方便其他元素移入。 另外，当元素不大于目标时，此时说明要插入目标的位置已经找到了。

翻译成代码：

let array = [1, 3, 5, 2, 4]
let i = 3
let target = array[3]
while(i > 0 && array[i-1] > target) {
  array[i] = array[i-1]
  i--
}
array[i] = target
console.log(array) // [ 1, 2, 3, 5, 4 ]
复制代码

能插入成功一个，遍历n-1次（第一个元素本身就是有序序列了），就可以全部插入，代码很容易写出来：

for (let j = 1; j < array.length; j++) {
  let i = j
  let target = array[i]
  while(i > 0 && array[i-1] > target) {
    array[i] = array[i-1]
    i--
  }
  array[i] = target
}
复制代码

完整代码：

const utils = {
  swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
  },
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function insertionSort(array) {
  for (let i = 1; i < array.length; 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
}
let array = utils.randomArray()
console.log(insertionSort(array))

至此，插入排序原理和实现已经说完了。