插入排序

插入排序像整理扑克牌一样工作：从左到右依次取出元素，将它插入到左侧已经有序的位置。

实现

js

function insertionSort(arr) {
  const result = [...arr]

  for (let i = 1; i < result.length; i++) {
    const current = result[i]
    let j = i - 1

    while (j >= 0 && result[j] > current) {
      result[j + 1] = result[j]
      j--
    }

    result[j + 1] = current
  }

  return result
}

复杂度

平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
最好时间复杂度：O(n)，数组接近有序时表现很好
空间复杂度：O(1)，不计算复制输入数组的空间
稳定性：稳定

插入排序实现简单、额外空间少，对小规模或基本有序的数据非常有效。