插入排序

1. 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

当前面的数更大，把大的数往后挪

当前面的数更小，说明前面的数都是比他小的数了，停止比较

2. 动图演示

3.代码演示

let array = [5,9,3,5,6,4,96,3,4,6,41,3,45,3,2,3,5,63,4,3,2]

// 插入排序函数
function insertionSort (arr) {
  // 开始遍历数组，从索引1到最后
  for (let i = 1; i < arr.length; i++) {

    // 被比较的数，其前面的数的index，后面通过preIndex--,获得更前面的数
    let preIndex = i - 1
    // 当前被比较的数
    let num = arr[i]

    // 当前面的数更大，把大的数往后挪
    // 当前面的数更小，说明前面的数都是比他小的数了，停止比较
    while (preIndex >= 0 && arr[preIndex] > num) {
      // 把大的数往后挪
      arr[preIndex + 1] = arr[preIndex]
      // 继续比较更前面的数
      preIndex--
    }
    // 把被比较的数放到合适位置
    arr[preIndex + 1] = num

    // 每次遍历，看看变化
    console.log(arr);
  }
}

insertionSort(array)