位置: 编程技术 - 正文

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)

  • 未按规定缴纳保险
  • 我国当前税制结构的基本情况是怎样的
  • 股份有限公司董事会决议必须经过
  • 小规模减免增值税要交企业所得税吗
  • 税控盘费用进什么科目
  • 核定征收季度核定销售额
  • 营改增之前的房产出售税率
  • 商品流通企业的资金循环
  • 申报个人所得税的详细流程
  • 电子发票如何查询发票代码
  • 小规模纳税人免税怎么做账
  • 缴纳滞纳金计入什么科目
  • 企业所得税季报怎么申报
  • 公司利润怎么提出来给老板
  • 一张抵扣发票能分多次抵扣不
  • 贴现扣的钱叫什么
  • 低值易耗品属于资产类
  • 软件企业销售服务符合增值税即征即退吗
  • 土地增值税进项税
  • 纳税人月销售额怎么算
  • 生产成本在资产负债表中怎么填
  • 网络限速数值
  • php判断ua
  • 股息红利要交税吗
  • 公司卖旧车税务处理流程
  • 借条丢了怎么办打电话给家长
  • 应收账款债权融资计划业务操作指引
  • 生产企业一般贸易
  • 跨域的几种方法
  • vue插槽使用
  • 车船税每年都要多少钱
  • 研发费用资本化计入什么科目
  • 工程项目发票几个点
  • python的多线程 吃cpu太厉害
  • python数组合并并排序
  • 企业自查补税怎么报税
  • 火车票丢了还能再取吗
  • 取得股息红利所得 个人所得税
  • 金蝶结转销售成本
  • 房租付了没有及时取得发票怎么入账
  • 预付工程款会计分录
  • 收到捐赠的账务处理和涉税处理
  • 招待客人会计分录
  • 双倍余额递减法计提折旧公式
  • 预付卡销售和充值怎么做账
  • 暂扣员工工资应怎么处理
  • 固定资产售后回租融资租赁利息可以抵扣进项税额么
  • 注册资本为0的公司可以去吗
  • 小规模一直零申报有什么影响
  • 存货成本计算方法有几种?分别是什么?
  • 独立法人资格是独立核算
  • 新组建的公司该怎样开展工作
  • 债务重组的方式主要包括哪些
  • 会计科目设置的相关注意事项
  • windows下用什么编程工具
  • windowsxp服务在哪里
  • centos7.4升级7.5
  • u盘安装win10ghost
  • win8 u盘启动
  • 为什么win7系统盘会自动满
  • win8如何切换用户登录
  • win10太麻烦了
  • win7强制关机后内存不足
  • win8适用的pr
  • linux file-nr
  • opengl入门教程(精)
  • 批处理bat
  • 用原生js写项目
  • js格式化日期yyyy-mm-dd hh:mm:ss
  • nodelink
  • [置顶]bilinovel
  • jquery点击按钮跳转页面
  • 详细分析使用AngularJS编程中提交表单的方式
  • 让图片跳跃起来怎么弄
  • domcer下载
  • css中position的用法
  • 企业取得了哪些成绩
  • 威科先行法律信息库价格
  • 陕西省税务发票查询系统
  • 劳务包含哪些
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设