前端javascript中的排序算法之插入排序

插入排序（Selection Sort）基本思想：
插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着，
它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排
序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢？），以此类推。

代码实现

function insertSort(arr) {
  const len = arr.length;
  let j, tmp;
  //默认第一项已经排序
  for (let i = 1; i < len; i++) {
    j = i;
    //临时记录的变量
    temp = arr[i];
    //比较
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    //插入
    arr[j] = temp;
  }
  return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度

• 空间复杂度(O(1)),也是一种原址比较
• 时间复杂度O(n²)

代码测试

  var arr = [1, 67,45,30, 89, 10,23];
  const ret = insertSort(arr);
  console.log("
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/820805