码云笔记前端博客
Home > JavaScript > 前端开发必会的JS算法之插入排序

前端开发必会的JS算法之插入排序

2019-11-01 分类:JavaScript 作者:管理员 阅读(52)

本文共计1395个字,阅读时间预计4分钟,干货满满,记得点赞加收藏哦

上一篇我们说了经典排序中的选择排序,本文我们来看一下插入排序,所谓“插入”,实指把待排序元素插入到已排好的序列里。
前端开发必会的JS算法之插入排序
上图演示了第4次遍历,此时元素1、3、5已经是有序序列,待排的元素是2,要把它插入到1和3之间。此时3和5都往后移动了一位。

可以看出该算法的核心是:如何在有序序列里找到正确的插入位置?

思路是从有序序列的尾部开始,逐个与目标元素比较,如果大于目标元素,该元素需要后移。。
前端开发必会的JS算法之插入排序
可以看出之所以先要缓存一下目标,是为了要把它的位置先空下来,方便其他元素移入。 另外,当元素不大于目标时,此时说明要插入目标的位置已经找到了。

翻译成代码:

1
2
3
4
5
6
7
8
9
let array = [1, 3, 5, 2, 4]
let i = 3
let target = array[3]
while(i > 0 && array[i-1] > target) {
  array[i] = array[i-1]
  i--
}
array[i] = target
console.log(array) // [ 1, 2, 3, 5, 4 ]

能插入成功一个,遍历n-1次(第一个元素本身就是有序序列了),就可以全部插入,代码很容易写出来:

1
2
3
4
5
6
7
8
9
for (let j = 1; j < array.length; j++) {
  let i = j
  let target = array[i]
  while(i > 0 && array[i-1] > target) {
    array[i] = array[i-1]
    i--
  }
  array[i] = target
}

查看完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const utils = {
  swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
  },
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i
    let target = array[j]
    while(j > 0 && array[j-1] > target) {
      array[j] = array[j-1]
      j--
    }
    array[j] = target
  }
  return array
}
let array = utils.randomArray()
console.log(insertionSort(array))

至此,插入排序原理和实现已经说完了。

这里总结一下,插入排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为O(n^2),适用于少量数据排序。相比冒泡排序和选择排序,插入排序的使用相对多一些。因为前两者是交换排序,本质上需要3次原子操作的。

插入排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是找到正确的插入位置,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。

以上就是前端开发必会的JS算法之插入排序的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持码云笔记!

本系列已经发表文章:
前端开发必会的JS算法之冒泡排序
前端开发必会的JS算法之选择排序

「除特别注明外,本站所有文章均为码云笔记原创,转载请保留出处!」

赞(7) 打赏

觉得文章有用就打赏一下文章作者

支付宝
微信
7

觉得文章有用就打赏一下文章作者

支付宝
微信

上一篇:

下一篇:

你可能感兴趣

共有 0 条评论 - 前端开发必会的JS算法之插入排序

博客简介

码云笔记 mybj123.com,一个专注Web前端开发技术的博客,主要记录和总结博主在前端开发工作中常用的实战技能及前端资源分享,分享各种科普知识和实用优秀的代码,以及分享些热门的互联网资讯和福利!码云笔记有你更精彩!
更多博客详情请看关于博客

精彩评论

站点统计

  • 文章总数: 476 篇
  • 分类数目: 13 个
  • 独立页面: 8 个
  • 评论总数: 228 条
  • 链接总数: 15 个
  • 标签总数: 1050 个
  • 建站时间: 525 天
  • 访问总量: 8647866 次
  • 最近更新: 2019年11月21日