也作直接插入排序, 最稳定的算法, 来记录一下

更新

[2019-4-10]

  • Initial release

[2020-11-2]

Added

  • 新增代码实现

时间复杂度

O(n ^ 2)

空间复杂度

O(1)

思路

  • 外层遍历样本数
  • 内层遍历已排序数组
    • 未符合条件, 进位处理
    • 符合条件, 插入

源码

实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertSort(nums) {
  for(let i = 1; i < nums.length; i++) {
    let j = i - 1;
    let temp = nums[i];

    // 符合条件
    while(j >= 0 && nums[j] > temp) {
      nums[j + 1] = nums[j];
      j--;
    }
    // 不符合条件
    nums[j + 1] = temp;
  }

  return nums;
}

实现二

1
2
3
4
5
6
7
8
9
10
11
function insertSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = i; j > 0; j--) {
      if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      }
    }
  }

  return arr;
}