插入排序

什么是插入排序

什么是插入排序?想到插入我脑子里冒出来一个相近的词就是插队,我那时还在上大二,排在食堂一楼打饭,忽然来了一个没素质的一顿操作猛如虎地插到了我前面,唉,这人没救了!我当时就在想能不能用插入排序来描述这件事,后来发现不行,也就是说插队不是插入排序生活中的体现。我想到一个更为恰当的例子,那就是打扑克打双扣,有经验的选手他往往是这样的,右手抓到一张牌放入左手,然后右手再去抓一张牌去跟左手的牌作对比,如果比它小就放前面,比它大就放后面,重复楼上的动作,直到这位选手抓完27张牌后,他的左手应该握有一把美丽的扇子。好的,在理解完插入排序生活中的例子后,我们开始给它下个定义:

给定一组数据集,遍历这组数据集,每次拿当前遍历的元素与其前面元素的有序数据集的元素进行比较,将其插入相应的位置,我们将这种排序算法称之为“插入排序”。

实现一个插入排序

思路

大致是这样子,在已给定的数据集中,我们先拿第一个和第二个元素比大小排序,之后进行第二次循环,我们将第三个元素与已经排好序的第一个和第二个数据集中的元素进行比大小,将其插入合适位置,重复这个行为直至遍历到最后一个元素,至此,排序完成。

code

export default (arr) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
  }
  return arr;
}

test

test case

import insertSort from '../src/insert';


test('insert sort: test case 1', () => {
  expect(insertSort([2, 4, 3, 1])).toEqual([1, 2, 3, 4]);
});

test('insert sort: test case 2', () => {
  expect(insertSort([2, 0, 2, 0])).toEqual([0, 0, 2, 2]);
});

test('insert sort: test case 3', () => {
  expect(insertSort([1, 9, 9, 7])).toEqual([1, 7, 9, 9]);
});

test('insert sort: test case 4', () => {
  expect(insertSort([0, 6, 1, 3])).toEqual([0, 1, 3, 6]);
});

test result

PS E:\document\repos\JavaScript-Tsukuki\code\sort-study> npm run test:insert

> sort-study@1.0.0 test:insert E:\document\repos\JavaScript-Tsukuki\code\sort-study
> jest test/insert.test.js

 PASS  test/insert.test.js
  √ insert sort: test case 1 (5 ms)
  √ insert sort: test case 2
  √ insert sort: test case 3
  √ insert sort: test case 4

Test Suites: 1 passed, 1 total
Tests:       4 passed, 4 total
Snapshots:   0 total
Time:        7.645 s, estimated 22 s
Ran all test suites matching /test\\insert.test.js/i.
PS E:\document\repos\JavaScript-Tsukuki\code\sort-study>

本文选自Javascript筑基专题,项目地址:https://github.com/ataola/JavaScript-Tsukuki

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 选择排序

    最近看了一则寓言故事跟童鞋们分享一下,讲的是大山深处的神坑(为了激发大家的想象力,这里我就不画画了,请同学们自行脑补)。事情是这样子的,旁白站在上帝视角抛出一个...

    丰臣正一
  • FE[0x02] -- 浅谈CSS布局

    最开始网页有个p的布局,基本上打开大屁股头电脑能看文字就好了,再后来随着Web技术的发展,你可以选择浮动布局float,也可以结合position进行布局,还...

    丰臣正一
  • 使用jest进行单元测试

    不扯犊子直接说吧,第一点,用数据、用茫茫多的测试用例去告诉使用者,你的程序是多么鲁棒健壮;第二点,把它作为一种素养去培养吧,当你按照一系列规范去做事,那么你做出...

    丰臣正一
  • nodejs最简单的几行代码实现http输出文件

    小贝壳
  • 【C语言笔记】C语言编译的过程

    如果你使用的是集成开发环境,那么你点击编译按钮就可生成可执行文件,然后点击运行即可运行。那么,你知道从源代码到可执行文件经历了哪些过程吗。仅仅是编译?

    正念君
  • Google Test(GTest)使用方法和源码解析——Listener技术分析和应用

            在《Google Test(GTest)使用方法和源码解析——结果统计机制分析》文中,我么分析了GTest如何对测试结果进行统计的。本文我们将解...

    方亮
  • python的os遍历

    os.walk(top) 此方法默认只需要输入起始路径参数,它会返回一个迭代的对象,迭代出来是一个元组对象,里面有3个数据,第一个起始路径下的目录,第二个是这个...

    py3study
  • 前端面试题汇总

    (1) vue.js 兄弟组件通信 生命周期 vue router vuex 原理 (2) angular (3) react ...

    城市中的游牧民族
  • Android面向切面AOP架构设计后续补充

    假设 test 类里有使用到 @aop 的切点注解,那么我们在混淆文件中就应该 -keep 这个 test 类

    萬物並作吾以觀復
  • TensorFlow实现流行机器学习算法的教程汇总(3/3)

    IT派

扫码关注云+社区

领取腾讯云代金券