插入排序

插入排序和打扑克牌一样，摸到一张牌，然后和手里的每一张牌对比，把摸到的牌插入到正确位置（对比大小）。

算法步骤

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

动图演示

代码实现

// 插入排序
// 从小到大
// 循环次数为(n-1)+(n-2)+(n-3)+...+(n-(n-1)) => n(n-2)所以复杂度为O(n^2)
function insertionSort(arr) {
  // 排序轮数为 length - 1 次
  // 选择一个数，然后和前面已经排好序的进行比较
  for (let i = 1; i < arr.length; i++) {
    // 当前值比前面的已排序的最后一个元素小，说明需要排序，否则就不用排序了
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      const temp = arr[j]
      arr[j] = arr[j - 1]
      arr[j - 1] = temp
    }
    console.log(arr)
  }
  return arr
}

const arr = [6, 3, 5, 2, 4, 1]

insertionSort(arr)

console.log(arr)