插入排序

概念

将数组中的第一个元素看成有序序列, 也就是最初的参照点, 把从第二个元素到尾部所有元素都看成未排序序列. 开始遍历未排序序列, 将每个未排序元素插入到有序序列中它应该的位置, 如果未排序元素与有序序列中某个元素相同, 则将其放到有序序列该元素后面.

1. 从第一个元素开始, 该元素可以认为已经被排序;
2. 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
3. 如果该元素(已排序)大于新元素, 将该元素移到下一位置;
4. 重复步骤 3, 直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤 2-5.

function insertionSort(arr) {
  let n = arr.length
  let preIndex
  let current
  for (let i = 1; i < n; i++) {
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}