位置: 编程技术 - 正文

python编程实现希尔排序(编写python)

编辑:rootadmin

推荐整理分享python编程实现希尔排序(编写python),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:编程用python,编程python怎么用,python中编写程序,python编写程序,python编写程序,用python编写程序,编写python,用python编写程序,内容如对您有帮助,希望把文章链接给更多的朋友!

观察一下”插入排序“:其实不难发现她有个缺点:

  如果当数据是”5, 4, 3, 2, 1“的时候,此时我们将“无序块”中的记录插入到“有序块”时,估计俺们要崩盘,每次插入都要移动位置,此时插入排序的效率可想而知。

  shell根据这个弱点进行了算法改进,融入了一种叫做“缩小增量排序法”的思想,其实也蛮简单的,不过有点注意的就是:

增量不是乱取,而是有规律可循的。

希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

首先要明确一下增量的取法(这里图片是copy别人博客的,增量是奇数,我下面的编程用的是偶数):

第一次增量的取法为: d=count/2;

第二次增量的取法为: d=(count/2)/2;

最后一直到: d=1;

好,注意看图了,第一趟的增量d1=5, 将个待排记录分为5个子序列,分别进行直接插入排序,结果为(, , , , , , , , , )

第二趟的增量d2=3, 将个待排记录分为3个子序列,分别进行直接插入排序,结果为(, , , , , , , , , )

第三趟的增量d3=1, 对整个序列进行直接插入排序,最后结果为(, , , , , , , , , )

重点来了。当增量减小到1时,此时序列已基本有序,希尔排序的最后一趟就是接近最好情况的直接插入排序。可将前面各趟的"宏观"调整看成是最后一趟的预处理,比只做一次直接插入排序效率更高。

本人是学python的,今天用python实现了希尔排序。

输出:

python编程实现希尔排序(编写python)

>: [, , , , , , , , , 4]>>: [, , , , 4, , , , , ]>>: [4, , , , , , , , , ]>>: [4, , , , , , , , , ]

首先你得先会插入排序,不会你必然看不懂。

插入排序,即是对上图三个黄色框中的数进行插入排序。举个例子:,,,

直接看,<, 不用移动。接着看,<,那么后移,数据变为[,,,],接着比较<, 那么替换,变成[,,,]。其它同理,略。

这里有个问题,比如第二个黄色框[,4,],4<, 那往后移,接着4就替换第一个,数据变成[4,,],但是计算机怎么知道4就是在第一个啊&#;&#;

我的做法是,先找出[,4,]第一个数的下标,在这个例子中的下标为1。当要插入的数的下标大于第一个下标1时,才可以往后移,前一个数不可以往后移有两种情况,一种是前面有数据,且小于要插入的数,那你只能插在它后面。另一种,很重要,当要插入数比前面所有数都小时,那插入数肯定是放在第一个,此时要插入数的下标=第一个数的下标。(这段话,感觉初学者应该不大懂……)

为了找到第一个数的下标,最开始想的是用循环,一直到最前面:

在Debug时,发现用循环太浪费时间了,特别是当增量d=1时,直接插入排序为了插入列表最后一个数,得循环减1,直到第一个数的下标,后来我学聪明了,用下面的方法:

时间复杂度:

希尔排序的时间复杂度是所取增量序列的函数,尚难准确分析。有文献指出,当增量序列为d[k]=2^(t-k+1)时,希尔排序的时间复杂度为O(n^1.5), 其中t为排序趟数。

稳定性: 不稳定

希尔排序效果:

参考资料: 编程是我自己实现的。建议Debug看看运行过程

c++中八大排序算法

视觉直观感受若干常用排序算法

C#七大经典排序算法系列(下)

1.非系统的学习也是在浪费时间 2.做一个会欣赏美,懂艺术,会艺术的技术人

标签: 编写python

本文链接地址:https://www.jiuchutong.com/biancheng/375506.html 转载请保留说明!

上一篇:python实现解数独程序代码(python 数独破解器)

下一篇:python常见排序算法基础教程(排序方法python)

  • 以现金支付
  • 水处理产业链
  • 资产几百亿真的有那么多钱吗?
  • 进项税加计抵减生产性服务
  • 库存现金和银行存款的区别
  • 新车交车辆购置税需要什么材料
  • 无法支付的应付账款转销
  • 收回已作为坏账准备的应收账款会计分录
  • 行政事业单位专用材料费列支范围
  • 确认以前年度收入怎么做账
  • 多计提的工资怎么处理?
  • 股权转让收入属于什么
  • 本月进项大于销项怎么做会计分录
  • 营改增后如何纳税
  • 自然人增值税免税额
  • 增值税专用发票电子版
  • 公司注销时资本要交税吗
  • 个人房补申请书怎么办
  • 外经证作废流程
  • 公司的房产税如何征收
  • 模具费属于什么费用
  • 研发费用属于期余资产吗
  • 企业转让库存股,应按实际收到的金额
  • 商业承兑汇票到期兑现流程
  • 什么情况下可以认定为工伤
  • 为什么iphone手机闹钟定了不响
  • 用银行存款支付明年的财产保险费
  • 存货报废会计分录例题
  • 车辆购置税的计税基础
  • hp workwise service是什么
  • 酒店里用了收费的东西怎么算
  • 布鲁克斯岭
  • 增值税减免附加税怎么处理
  • smart模板教程
  • mount.nfs an incorrect mount
  • 换货和退货有什么区别
  • 税务端系统返回错误信息f50006
  • 注销对公账户要去原支行吗
  • 报废产品需要入库吗
  • 跨年的发票可以退税吗
  • 去年发生了什么
  • python generation
  • 根据《中华人民共和国食品安全法》
  • access导入到mysql
  • 资产处置开票填什么项目
  • 分公司注销怎么起诉公司
  • 税局预缴增值税选错月期
  • 企业所得税季报是填累计数吗
  • 以前期间留抵税额是什么意思
  • 研发过程4个主要阶段
  • 专利年费可以减免吗
  • 应付票据在资产负债表怎么填列
  • 建账选用什么会计制度
  • mysql怎么复制粘贴语句
  • sql server查询
  • mysql很卡
  • 超级本可以玩游戏吗
  • qqprotect.exe是什么进程?qqprotect.exe怎么禁止自动启动?
  • win10分辨率2560*1080
  • 360win7
  • windows10周年更新
  • linux添加系统调用的步骤
  • pavprot.exe - pavprot是什么进程 作用是什么
  • win10系统怎么一键返回桌面
  • Linux基本命令使用
  • win7系统弹出好多停止运行程序
  • unity 读取txt
  • 可视化gradcam
  • jquery移动div到另一个div中
  • Node.js中的全局变量有哪些
  • 每天自动重启命令
  • js修改css文件
  • jquery div滚动条
  • python定制函数
  • 宁波地铁支付宝可以刷吗
  • 境外取得收入申报期限
  • 12366纳税服务平台人工时间
  • 重庆地税局官网公众号
  • 北京市国家税务局网站官网
  • 江西国家税务局电子税务局官网
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设