专栏首页技术面面观直接插入排序

直接插入排序

中华

诗词

登鹳雀楼

唐·王之涣

白日依山尽,黄河入海流。

 欲穷千里目,更上一层楼。

面试官:聊聊插入排序

插入排序是一种比较简单直观的排序算法,适用处理数据量比较少或者部分有序的数据,今天我们来聊聊插入排序。

排序思想

师傅,抄经书好无聊啊,要不咱们玩斗地主吧

一尘

慧能

好啊,但在此之前你先回答我几个问题

哦?什么问题

一尘

只见慧能拿出了一副牌,洗了洗牌,然后放在桌子上,从牌顶摸了几张牌

慧能

这些牌我已经手动排好序了

说着说着慧能又摸了一张牌

慧能

你说我这张红桃7该插入哪里呢?

红桃5和黑桃8之间

一尘

一尘不假思索地回答道

慧能

你是怎么判断要插入这里呢?

怎么判断?这一下还把小一尘给问愣住了,但是细想了一下整个过程,一尘答道

我觉得我的大脑是先将最后边的9和7比较,如果9大于7,则再拿8和7比较,直到找到不大于7(小于等于)的一张牌为止,然后将7插入到这张牌后面

一尘

慧能

恩恩,不错,这就是直接插入排序的主要思路

突然之间又学了一个知识点,每次知识都来得猝不及防

,一尘心里想到

慧能

所谓直接插入排序,就是把未排序的元素一个一个地插入到有序的集合中,插入时就像你那样,把有序集合从后向前扫一遍,找到合适的位置插入

慧能拿来了笔和纸准备详细地说说

慧能

比如说我手中有这么一副牌

慧能

我把左边第一个8看做已经排好序的牌,右边的5,3,9都是未排好序的

慧能

然后我将5按照你的方法插入到排好序的集合中,显然,它会插到最左边

慧能

然后把3插入到排好序的集合

慧能

9同理

代码

哦,我懂了,原来直接插入排序这么简单

一尘

慧能

那你用代码实现一下呗

早知道就不说这句话了

,一尘心里想,但师命难违,还是硬着头皮想了想

首先我用一个数组存储要排序的数据(无序)

然后我用for循环从前到后遍历整个数组,将无序元素一个一个地插入到正确的位置(排好序的位置),第一个元素我认为它是排好序的,所以我从第二个元素开始遍历

随后,小一尘写下了如下代码

数组下标从0开始,所以从1开始遍历,一直遍历到最后一个元素(arr.length-1)

一尘

一尘解释道

慧能

你这个插入到正确位置的函数是怎么实现的?

是啊,这个怎么实现呢?咦,我可以用一个临时变量把待插元素(将要插入到有序集合的元素)存起来,然后逐个和有序集合里的元素比较,如果集合里的元素大于待插元素,就将它向后移动一个单元,这样当遇到有序集合中小于等于待插元素的元素时就有地方放待插元素了

小一尘又把插入方法(insertToRightPosition)实现了

i 指向待插元素,j 会遍历有序数组中所有元素,直到找到合适的位置将待插元素(inserted)插入

一尘

慧能

恩恩,不错嘛!看来编码能力还行,那你说说你的这个代码的时间复杂度

时间复杂度

这个...,让我想想

一尘

下面讨论最坏时间复杂度,即所有元素倒序

这段代码最耗时的地方就花在最内层for循环里面的操作上(比较和移动)了,我只要大概估算出这些操作执行的次数就可以了

对于n个元素,首先我的外层for循环要循环n-1次

然后insertToRightPosition里的内层for循环的循环次数是根据 i 来决定的,i = 1时,循环 1 次,i = 2,循环 2 次,...,i = n-1,循环 n-1次,那总共加起来就是

根据复杂度计算规则,保留高阶项,并去掉系数,那么时间复杂度为O(n^2)

时间复杂度请看:

算法分析神器—时间复杂度

是O(n^2)

一尘

一尘说道

慧能

恩恩,不错,那算法的稳定性呢?

稳定性

是稳定的,因为在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变

一尘

慧能

恩恩,不错,走,下山玩斗地主去

好呀好呀

一尘

关于稳定性可以看:冒泡排序(文末有)

本文分享自微信公众号 - 编程三分钟(coding3min)

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

原始发表时间:2019-05-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 希尔排序

    希尔排序(ShellSort)是以它的发明者Donald Shell名字命名的,希尔排序是插入排序的改进版,实现简单,对于中等规模数据的性能表现还不错

    机智的程序员小熊
  • Git 版本控制,看这篇就够了 (二)基础篇

    摘要:完成本系列文章的阅读以后,你将掌握git的基本概念与git的基本命令,可以在本地随心所欲的完成代码的提交撤销保存修改等操作、可以流畅的参与多人协作,让我们...

    机智的程序员小熊
  • 到底是哪条SQL拖慢了你的数据库?

    开启慢查询日志,可以让MySQL记录下查询超过指定时间的语句,通过定位分析性能的瓶颈,才能更好的优化数据库系统的性能。

    机智的程序员小熊
  • 直接插入排序

    登鹳雀楼 唐·王之涣 白日依山尽,黄河入海流。  欲穷千里目,更上一层楼。 面试官:聊聊插入排序 插入排序是一种比较简单直观的排序算法,适用处理数据量比...

    用户1260737
  • Aliyun WinServer离线迁移到腾讯云

    在桌面输入快捷键win+r打开运行窗口,然后输入 diskmgmt.msc,按 Enter,打开 “磁盘管理”。

    jonnyzhao
  • Goscan:功能强大的交互式网络扫描工具

    GoScan是一款交互式网络扫描客户端,可用来执行主机扫描、端口扫描和服务枚举等任务。它不仅可在时间有限的情况下完成高难度任务,而且还支持进行专业的安全管理。

    FB客服
  • 给新生成的节点(动态生成节点)绑定事件方法总结

    第一种 jquery写法 $('.father').on('click',',child',function(){}) $(document).on('cli...

    吴裕超
  • Python 元类实现 ORM

    上一篇章大概讲述了元类的概念,实现使用元类的方式修改一个类的属性大小写修改的功能。

    Devops海洋的渔夫
  • 【网页】HTTP错误汇总(404、302、200……)

    原贴:http://blog.sina.com.cn/s/blog_68158ebf0100wr7z.html

    后端技术漫谈
  • 事务日志初探(二)---简单恢复模式

    简述     在简单恢复模式下,日志文件的作用仅仅是保证了SQL Server事务的ACID属性。并不承担具体的恢复数据的角色。正如”简单”这个词的字面意思一样...

    用户1217611

扫码关注云+社区

领取腾讯云代金券