位置: 编程技术 - 正文

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)

  • 计提所得税费用会计分录
  • 技术支持费用取费依据
  • 广告制作可以开什么发票
  • 绿化工程账务处理支出
  • 建筑企业预缴印花税会计分录
  • 广告传媒公司安全生产标准化
  • 所得税汇算清缴分录怎么做
  • 广告制作费可以计入印刷费吗
  • 车辆保险费的车船税计入什么会计科目
  • 施工费可以开13个点吗
  • 减免税费期末如何结转
  • 公司合作建房什么意思
  • 赞助失败案例
  • 废品损失科目月末
  • 农产品增值税核定扣除办法
  • 建筑劳务公司的会计账务处理
  • 劳务公司差额征收税率是多少
  • 即征即退收入是否计入三免三减半所得
  • 个体户定期定额申报表怎么填
  • 企业收取的延期付款利息需要征消费税和增值税
  • 关闭 ipv6
  • linux查杀webshell
  • 错误代码11-1114
  • 报销冲借款是什么意思
  • 代销商品手续费计入什么科目
  • 公司注销账上有固定资产转给股东还要交税吗
  • 联想小新Air15如何进入bois
  • 金税盘服务费怎么申报抵扣
  • PHP:stream_set_chunk_size()的用法_Stream函数
  • 消费税和增值税的征税范围有何不同
  • ros source
  • echarts地图tooltip
  • 本文虚构
  • thinkphp in
  • 投资中间人要担什么责任
  • php使用自定义函数编程求半径r的圆的周长和面积
  • 基于javaweb是什么意思
  • 微软 gcr
  • 疯狂世界百科
  • username命令
  • 事业单位收到的罚款收入应纳入
  • 计提本月工资社保怎么扣
  • 不动产投资应该怎么做账
  • mongodb安装使用
  • 应发工资包含
  • 高新技术企业收入总额
  • 进口货物的会计分录
  • 承包费会计处理
  • 公司给买员工保险
  • 没有发票会怎样
  • 余利宝本金会亏吗
  • 办公楼开始建造前专门借款的利息费用
  • 招待费进项税额可以抵扣吗
  • 合并报表怎么合并
  • 工资计提和发放账务处理
  • 房地产企业预付账款会计分录
  • 企业微信对公账户认证
  • pg 正则表达式
  • FastDFS4和Ubuntu12安装及部署步骤
  • linux系统
  • win8.1怎么用
  • win10 20h2 v2
  • windows7basic怎么改
  • Android NDK Cocos2dx 3.4 Label中文显示
  • 游戏引擎的重要性
  • pycharm如何使用
  • jquery过滤选择器案例
  • javascript 语言精粹(修订版)
  • 轻松实现的英文
  • 安卓怎么记录时间
  • 全国税务查询
  • 专用发票如何导出
  • 云南税务局网上办税大厅登录入口官网
  • 江苏税务开发票
  • 张江税务所地址
  • 港澳台资企业
  • 网上申报增值税纳税申报表怎么填写
  • 深圳市的各区域排名
  • 手写发票属于增值税普通发票吗
  • 税收分类分级管理后如何开展风险管理
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设