插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢），以此类推。

下面这段代码表示插入排序算法。

function insertionSort(array, compareFn = defaultCompare) {
  const { length } = array; // {1}
  let temp;
  for (let i = 1; i < length; i++) { // {2}
    let j = i; // {3}
    temp = array[i]; // {4}
    while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) { // {5}
      array[j] = array[j - 1]; // {6}
      j--;
    }
    array[j] = temp; // {7}
  }
  return array;
};

照例，算法的第一行用来声明代码中使用的变量（行{1}）。接着，迭代数组来给第i项找到正确的位置（行{2}）。注意，算法是从第二个位置（索引1）而不是0位置开始的（我们认为第一项已排序了）。然后，用i的值来初始化一个辅助变量（行{3}）并也将其值存储在一个临时变量中（行{4}），便于之后将其插入到正确的位置上。下一步是要找到正确的位置来插入项目。只要变量j比0大（因为数组的第一个索引是0——没有负值的索引）并且数组中前面的值比待比较的值大（行{5}），我们就把这个值移到当前位置上（行{6}）并减小j。最终，能将该值插入到正确的位置上。

下面的示意图展示了一个插入排序的实例。

举个例子，假定待排序数组是[3, 5, 1, 4, 2]。这些值将被插入排序算法按照下面的步骤进行排序。

(1) 3已被排序，所以我们从数组第二个值5开始。3比5小，所以5待在原位（数组的第二位）。3和5排序完毕。

(2) 下一个待排序和插到正确位置上的值是1（目前在数组的第三位）。5比1大，所以5被移至第三位去了。我们得分析1是否应该被插入到第二位——1比3大吗？不，所以3被移到第二位去了。接着，我们得证明1应该插入到数组的第一位上。因为0是第一个位置且没有负数位，所以1必须被插入第一位。1、3、5三个数字已经排序。

(3) 然后看下一个值：4。4应该在当前位置（索引3）还是要移动到索引较低的位置上呢？4比5小，所以5移动到索引3位置上去。那么应该把4插到索引2的位置上去吗？4比3大，所以把4插入数组的位置3上。

(4) 下一个待插入的数字是2（数组的位置4）。5比2大，所以5移动至索引4。4比2大，所以4也得移动（位置3）。3也比2大，所以3还得移动。1比2小，所以2插入到数组的第二位置上。至此，数组已排序完成。

排序小型数组时，此算法比选择排序和冒泡排序性能要好。

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>插入排序</title>
</head>

<body>

</body>
<script>
  function swap(array, a, b) {
    /* const temp = array[a];
    array[a] = array[b];
    array[b] = temp; */ // 经典方式
    [array[a], array[b]] = [array[b], array[a]]; // ES2015的方式
  }
  function defaultCompare(a, b) {
    return a < b ? 0 : 1
  }
  function insertionSort(array, compareFn = defaultCompare) {
    const { length } = array; // {1}
    let temp;
    for (let i = 1; i < length; i++) { // {2}
      let j = i; // {3}
      temp = array[i]; // {4}
      debugger;
      while (j > 0 && compareFn(array[j - 1], temp) === 1) { // {5}
        array[j] = array[j - 1]; // {6}
        j--;
      }
      array[j] = temp; // {7}
    }
    return array;
  };
  function createNonSortedArray(size) {
    const array = [];
    for (let i = size; i > 0; i--) {
      array.push(i);
    }
    return array;
  }
  let array = createNonSortedArray(5);
  console.log(array.join());
  array = insertionSort(array);
  console.log(array.join()); 
</script>

</html>

算法过程：

（1） 4 与 5 交换得到 4 ，5，3，2 ，1

（2） 5与 3交换得到 4 ，3，5，2，1 因为有 while 循环循环里面有条件我们这里还满足条件所以还得做循环

（3） 3与 4 交换得到 3 ，4，5 ，2， 1

类推就得到结果 1，2，3，4，5