插入排序

• 如何在一个有序数组中插入一个新的值？然后让这个数组继续保持有序状态

将 8 放到合适的位置，挨个比较，13 比 8 大，9 也比 8 大

• 问题抽象

function insert (A, x) {
  A: 已排序的数组

  x: 需要插入的元素

  返回值: 无
}

• javascript 的原始实现插入数字的过程

// 原始数组
const A = [2, 4, 7, 9, 13]
const x = 8 // 需要插入的元素

// b 代表第一个大于 x 的数字
const b = A.find(a => a > x)

// b === undefined 表示所有元素都比8小

if (b === undefined) {
  A.push(x)
} else {
  const idx = A.indexOf(b)
  A.splice(idx, 0, x)
}

// 51-56 行可以合并后写
const idx = A.indexOf(b)
// 如果找不到就放到最后一位，找到了，就放到idx的位置
A.splice(idx === -1 ? A.length : idx, 0, x)

• splice 语法

splice(开始位置，删除数，插入的元素1，插入的元素2，....)

图1-1

在有序数组 [2, 4, 7, 9, 13] 预留一个空位置，也就是图中的第一个绿色块 定义给一个指针p，p 的值指向的是下一个要比较的元素，而 p+1 指向的就是空位置，用来交换。

function insert (A, x) {
  // p 指向下一个需要比较的元素
  // p + 1 指向空位
  let p = A.length - 1 // 初始值 4
  while (p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}
// 原始数组
const A = [2, 4, 7, 9, 13]
// 需要插入的元素
const x = 8
insert(A, x)
console.log(A) // [2, 4, 7, 8, 9, 13]

上述代码的执行过程：

将数组中的值从最后往前挨个和 8 比较

• 第一次循环：A[p] > x => p = 4 13 > 8 条件成立执行循环体，将大的值(13)挪到空位去即：A[p + 1] = A[p] p--后值为3 继续比较下一个值，对应图中图1-1中 p = 4

• 第二次循环：A[p] > x => p = 3 9 > 8 条件成立执行循环体，将大的值(9)挪到空位即：A[p + 1] = A[p] p-- 后值为2 继续比较下一个值，对应图中图1-1中 p = 3

• 第三次循环：A[p] > x => p = 2 7 > 8 条件不成立，不执行while循环，此时 p = 2， 执行A[p + 1] = x 即8 放到 3 的位置，操作执行完成。

• 完整的插入排序计算过程

图1-2

function insertion_sort (A) {
  for (let i = 1; i < A.length; i++) {
    // A 数组
    // i 数组的前 i 项，已排好序了
    // A[i] 表示未排序的元素
    insert(A, i, A[i])
  }
}

function insert(A, i, x) {
  let p = i - 1 // 从第 0 个元素开始
  
  // 位置交换，如果当前元素A[p] 大于要比较的元素x
  while (p >= 0 && A[p] > x) {
    // i = 1 p = 0 从最后一个元素比较，此时只有一个元素
    // i = 2 p = 1 
    // i = 3 p = 2
    // ....
    A[p + 1] = A[p]
    p--
  }
  // 当前 元素A[p]不大于 x 的时候，那么就把 x 放到下一个位置
  // x 回写
  A[p + 1] = x
}

const A = [5, 8, 1, 3, 2, 4, 9]
insertion_sort(A)
console.log(A) // [1, 2, 3, 4, 5, 8, 9]

• 原理动图

图1-3