插入排序

问题抽象

A: 已排序数组 x: 需要插入得元素没有返回值

首先 JavaScript 原始实现方式

const a = [1,3,5,7,88]
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)
}

// 优化代码 我们直接 indexOf 获取 b 的位置
const a = [1,3,5,7,88]
const x = 8
// b 代表 第一个大于x得数字
const b = a.find(a => a > x)

const idx = a.indexOf(b)
a.splice(idx === -1 ? a.length : idx, 0 , x)

const a = [1,3,5,7,88]
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)
}

// 优化代码 我们直接 indexOf 获取 b 的位置
const a = [1,3,5,7,88]
const x = 8
// b 代表 第一个大于x得数字
const b = a.find(a => a > x)

const idx = a.indexOf(b)
a.splice(idx === -1 ? a.length : idx, 0 , x)

那我们如何使用程序来完成实现上述过程

每次拿绿色的指针元素跟我们插入的元素进行比较每次对比都会向左递减方向


function insert(A, x) {
  // p 指向下一个需要比较的元素
  // p + 1 指向空位
  let p = A.length - 1;

  while(p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}


function insert(A, x) {
  // p 指向下一个需要比较的元素
  // p + 1 指向空位
  let p = A.length - 1;

  while(p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}

完整的插入排序

function insert(A, i,x) {
  let p = i - 1;
    while(p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}
function insertion_sort(A) {
  for(let i = 1; i < A.length; i++) {
    insert(A, i , A[i])
  }
}

function insert(A, i,x) {
  let p = i - 1;
    while(p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
}
function insertion_sort(A) {
  for(let i = 1; i < A.length; i++) {
    insert(A, i , A[i])
  }
}

在github 上编辑文档

插入排序 ​

插入排序