排序：插入排序

原理

插入排序，顾名思义，以“插入”来实现排序。
那怎么插入呢？
以数组来说，插入是将一个元素放到一个有序数组的适当位置，保证插入后的数组依然有序。
我们可以将一个数组拆分成有序和无序两部分，然后将无序数组当中的元素一个个插入到有序的数组中。

例子

假如给定一个无序数组：

[5, 2, 7, 3]

要求将这个数组进行升序排列。

首先将这个数组拆分成两个部分：

[(5), (2, 7, 3)]

左边的部分只有一个元素，我们将它视为有序的。
然后将右边部分的元素一个个插入左边。

[(5, 2), (7, 3)]

此时，2 是新插入的元素。将它与原来的 5 比较，发现比 5 小，所以将它移动到适当的位置：

[(2, 5), (7, 3)]

此时，左边的数组保持有序。

接下来插入的元素是 7。

[(2, 5, 7), (3)]

待插入的元素依次与它左边的元素比较。这里是 7 和 5 比较。
发现 7 比 5 大，所以直接将 7 放在左边的末尾即可，无需再移动位置。

这里需要注意的是，在 7 插入之前，左边是有序的，可知最大的元素 5 就在末尾。
而新插入的 7 比左边的最大元素还大，可直接放到末尾，无需再与左边的其它数字比较。
我好啰嗦。

然后我们将右边部分的最后一个数字 3 插入左边的部分。

[(2, 5, 7, 3),()]

右边空了。将 3 依次与左边原来的数字比较。

3 与 7 比，比 7 小，所以放在 7 左边:

[2, 5, 3, 7]

接下来与 5 比，比 5 小，放在 5 左边：

[2, 3, 5, 7]

然后和 2 比， 比 2 大。好，辛苦了，不用动了。

这样就排好了：

[2, 3, 5, 7]

代码

/**
 * 指定数组，交换数组中两个元素的位置
 * @param {Array} list 数组
 * @param {Number} i 元素 1 的索引
 * @param {Number} j 元素 2 的索引
 */
const swap = (list, i, j) => {
  let temp = list[i]
  list[i] = list[j]
  list[j] = temp
}

// 插入排序
const insertSort = (list) => {

  for (let i = 1; i < list.length; i++) {
    for (let j = i; j > 0 && list[j] < list[j - 1]; j--) {
        swap(list, j, j - 1)
    }
  }

  return list
}

代码中的索引 i 以及 i 之前的元素可理解为数组左边的部分，j 即是新插入元素的索引。