风动之石的博客

插入排序

示意图

插入排序示意图

实现

function insertionSort(arr) {
  const len = arr.length
  for (let i = 1; i < len; i++) {
    let key = arr[i]
    let j = i - 1
    while(j >= 0 && key < arr[j]) {
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = key
    console.log(arr)
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分析

注意：如果插入时发现前一位置与插入值相等，则插入在其后。

优化

二分法插入排序

function insertionSort(arr) {
  const len = arr.length
  for (let i = 1; i < len; i++) {
    let key = arr[i]
    let left = 0, right = i - 1
    while(left <= right) {
      let middle = Math.floor((left + right)/2)
      if (key < arr[middle]) {
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    for (let j = i - 1; j >= left; j--) {
      arr[j+1] = arr[j]
    }
    arr[left] = key
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Reference