插入 | Autumn 博客

/* 插入排序 */
function insertionSort(nums) {
  // 外循环：已排序区间为 [0, i-1]
  for (let i = 1; i < nums.length; i++) {
    let base = nums[i],
      j = i - 1
    // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
    while (j >= 0 && nums[j] > base) {
      nums[j + 1] = nums[j] // 将 nums[j] 向右移动一位
      j--
    }
    nums[j + 1] = base // 将 base 赋值到正确位置
  }
}

let arr = [64, 34, 25, 12, 22, 11, 90]

// 34, 64, 25, 12, 22, 11, 90
console.log('排序前的数组: ', arr)
let sortedArr = insertionSort(arr)
console.log('排序后的数组: ', sortedArr)

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2)。