linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

算法排序 - 插入排序法

时间:2019-11-20  来源:未知  作者:admin666

正文

接下来我来讲述一下插入排序法。

首先来解释一下插入排序法的原理,它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序,也就是要找到新插入的数对应原序列中的位置。那么也就是说,每次插入一个数都要对原来排序好的那部分序列进行重新的排序,时间复杂度同样为O(n²)。 这种算法是稳定的排序方法。

直接插入排序算法分析

根据代码我们来解释一下直接插入排序的核心

例如,我们要对5,3,4,6,2这几个数进行排序

a[]01234
5 3 4 6 2

当这个数组进入函数后,下标首先定义到i = 1,即排序前,首先定义为a[0] = 5即是有序的。

进入循环内,比较a[1] 是否小于 a[0] 发现是小于的,这个时候按理说是要把a[0]这个元素右移动1位。然后将a[1]这个元素插在a[0]的位置上

但是考虑到这样子将覆盖原来的a[1]的值,所以先将a[1]的值拷贝一份给temp,然后将a[0]右移一位,再将temp的值传给a[0] .即

a[]01234
3 5 4 6 2

这时i =2了。此时a[0],a[1]属于有序的序列了,我们此时再次比较a[2]是否小于a[1](前一位),4<5,满足if条件

temp = a[2] 先拷贝一份,再将a[1] 右移一位,再次比较a[0]是否大于temp ,发现3并没有大于4,由此可见只要i前面有序数存在大于a[i]的值,有序序列就要向后移动,

然后再把a[i] 插在正确的位置。

a[]01234
3 4 5 6 2

当i = 3时,这个时候6比5大,不满足if条件,也可以发现,前面已经都是有序序列{3,4,5,6}.

最后当i = 4时,发现2 < a[3] 这个时候同理前面操作,先将a[4]拷贝一份给temp ,a[4] = a[3],右移一位

再次比较 ,发现temp < a[2] , a[3] =a[2] ,右移一位

再次比较 ,发现temp < a[1] , a[2] =a[1] ,右移一位

再次比较 ,发现temp < a[0] , a[1] =a[0] ,右移一位

此时就可以把temp 赋值给了a[0] ,这个时候就已经排序完成了。

a[]01234
2 3 4 5 6

直接插入排序复杂度分析

从空间上看,它只需要一个辅助空间temp ,因此我们关键看它的时间复杂度。

当最好的情况下,也就是序列本身就是有序的 ,这个时候我们只有进行每次的if判断(第20行),比较的次数n-1,移动的次数0,这个时候时间复杂度O(n)

image

如果排序记录是随机的话,那么根据概率相同的情况原则,平均比较和移动的次数约为(n^2)/4 次,因此我们可以得出直接插入排序法的书剑复杂度为O(n^2) 从这里也可以看出

直接插入排序比冒泡排序和简单选择排序性能要好一点,是一个稳定的排序算法。

linux
友情链接
  • Mozilla发布Firefox 67.0.4,修复沙箱逃逸漏洞
  • 蚂蚁金服正式成为CNCF云原生计算基金会黄金会员
  • Firefox 68将采用Microsoft BITS安装更新
  • OpenSSH增加对存储在RAM中的私钥的保护
  • 谷歌想实现自己的curl,为什么?
  • Raspberry Pi 4发布:更快的CPU、更大的内存
  • Firefox的UA将移除CPU架构信息
  • Ubuntu放弃支持32位应用程序实属乌龙,Steam会否重回Ubuntu怀抱
  • Qt 5.13稳定版发布:引入glTF 2.0、改进Wayland以及支持Lottie动
  • 红帽企业Linux 7现已内置Redis 5最新版
  • Slack进入微软内部禁用服务清单,GitHub也在其列?
  • 安全的全新编程语言V发布首个可用版本
  • Windows Terminal已上架,快尝鲜
  • 阿里巴巴微服务开源生态报告No.1
  • 面世两年,Google地球将支持所有基于Chromium的浏览器
  • 推进企业容器化持续创新,Rancher ECIC千人盛典完美收官
  • CentOS 8.0最新构建状态公布,或于数周后发布
  • Debian移植RISC
  • 微软拆分操作系统的计划初现雏形
  • Oracle发布基于VS Code的开发者工具,轻松使用Oracle数据库
  • Ubuntu 19.10停止支持32位的x86架构
  • 微软为Windows Terminal推出全新logo
  • 联想ThinkPad P系列笔记本预装Ubuntu系统
  • 微软发布适用于Win7/8的Microsoft Edge预览版
  • 启智平台发布联邦学习开源数据协作项目OpenI纵横
  • 经过六个多月的延迟,微软终于推出Hyper
  • ZFS On Linux 0.8.1 发布,Python可移植性工作
  • DragonFly BSD 5.6.0 发布,HAMMER2状态良好
  • Linux Kernel 5.2
  • CentOS 8.0 看起来还需要几周的时间
  • 百度网盘Linux版正式发布
  • PCIe 6.0宣布:带宽翻倍 狂飙至256GB/s
  • PHP 7.4 Alpha 发布,FFI扩展,预加载Opcache以获得更好的性能
  • Canonical将在未来的Ubuntu版本中放弃对32位架构的支持
  • Scala 2.13 发布,改进的编译器性能
  • 微软的GitHub收购了Pull Panda,并且使所有订阅完全免费
  • Windows Subsystem for Linux 2 (WSL 2)现在适用于Windows 10用
  • Debian 10 “Buster”的RISC
  • MariaDB宣布发布MariaDB Enterprise Server 10.4
  • DXVK 1.2.2 发布,带来微小的CPU开销优化
  • DragonFlyBSD 5.6 RC1 发布,VM优化,默认为HAMMER2
  • PrimeNG 8.0.0 发布,支持Angular 8,FocusTrap等
  • GIMP 2.10.12 发布,一些有用的改进
  • 清华大学Anaconda 镜像服务即将恢复
  • Debian GNU/Linux 10 “Buster” 操作系统将于2019年7月6日发布
  • 时时彩论坛
  • 五星体育斯诺克
  • 北单比分直播
  • 河北11选5走势图
  • 福建体彩36选7开奖结果
  • 九龙图库下载