3. 插入排序

算法描述

插入排序是一种比较直观的排序方法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

动图演示

算法实现

这里需要注意的地方也是边界的情况，如果在往后移动的过程发现到头了 j === 0，则可以直接将头部位置赋值为新元素。

/**
 * 插入排序
 * @param {number[]} arr 数组
 */
const insertionSort = (arr) => {
  let current
  for (let i = 1; i < arr.length; i++) {
    current = arr[i]
    for (let j = i - 1; j >= 0; j--) {
      if (current < arr[j]) {
        arr[j + 1] = arr[j]
        if (j === 0) arr[j] = current
      } else {
        arr[j + 1] = current
        break
      }
    }
  }
  return arr
}