插入排序

实现思路

• 从第二个数开始往前比
• 前一个比它大就往后排
• 以此类推

代码描述

const insertionSort = arr => {
  for (let i = 1; i < arr.length; i += 1) {
    let compare = arr[i]
    let j = i
    while (j > 0 && compare < arr[j - 1]) {
      arr[j] = arr[j - 1]
      j --
    }
    arr[j] = compare;
  }
  return arr;
}

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)