位置: 编程技术 - 正文

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)

  • 个人所得税年终奖单独计税怎么操作
  • 小微企业减半征收印花税代码
  • 小规模纳税人月收入多少免征增值税
  • 金银首饰销售需求分析
  • 生育津贴是否需要纳税
  • 横幅属于什么税收大类?
  • 一般纳税人给小规模开普票是几个点
  • 小规模纳税人季度多少免税
  • 服务,不动产和无形资产扣除项目本期实际扣除金额
  • 合同方和付款方不一致,发票开付款方可以吗
  • 定额材料损耗率国家标准
  • 材料成本差异怎么理解
  • 当月未开发票增值税怎么报
  • 零售环节销售金额标准
  • 支付境外个人佣金
  • 五险一金缴税基数
  • 开错的发票正常入账吗
  • 清包工和甲供工区别在哪
  • 个体工商户增值税税率2023年
  • 公立医院规章制度
  • 固定资产不动产和动产的区别
  • 母公司资产转移到子公司
  • 质量扣款发票怎么处理
  • 专业服务业政策
  • 现金股利属于什么所得
  • 资产负债表总计数表示什么意思
  • ghost读不出硬盘
  • 利空啥意思
  • mac设置邮件
  • php curl header参数
  • 电子设备摊销额怎么算
  • 如何才能显示效果更好
  • phpif判断语句
  • 购买货物现金付讫的会计分录
  • uniapp微信小程序头像获取与服务器对接
  • 解除劳动合同后需要把合同拿回来吗
  • 生产企业自营出口应税消费品
  • 蒂内河畔圣艾蒂安小镇,法国阿尔卑斯省 (© CAVALIER Michel/hemis.fr/Alamy Stock Photo)
  • 公司的财产保险包括哪些
  • 预收账款和应收账款的转换
  • 为什么很多银行卡会被异地警方冻结
  • phpstudy目录
  • php如何安装配置
  • 分公司要不要银行开户
  • 个税可以补申报几个月的码
  • 材料已经入库但是没有发票怎么做账
  • 长期待摊费用的最新账务处理
  • 全年多少钱就得交税
  • 增值税补充申报表不填可以吗
  • 让渡资产使用权包括
  • 小规模免税收入是多少
  • 盘亏的主要原因是什么
  • 增值税是不是不用计提
  • 公司的旅游费怎么处理
  • 其他应收款项
  • 财务报表中的存货包括哪些内容
  • 成本增加比例怎么算的
  • 删除一组数据中的指定数据
  • 锁mysql
  • windows10的设置在哪里
  • centos的优缺点
  • 怎么在mac上看电视剧
  • windows7升级到win8
  • linux中docker
  • 修改win10登录界面
  • linux bye
  • unity Toggle Groud
  • 实用的批处理
  • javascript的prompt
  • 安卓颜色值代码表
  • vue 组件打包为npm
  • jquery实现移动端
  • jquery示例
  • flask框架图
  • 临沂市国家税务局人员名单
  • 诺诺发票怎样上报汇总
  • 车辆购置税查询怎么查
  • 合格的税务人
  • 国税湖南电子税务局官网
  • 印花税会计分录怎么做 印花税需要计提吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设