前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python | 深入希尔排序世界

Python | 深入希尔排序世界

作者头像
算法与编程之美
发布2021-07-30 10:48:11
3250
发布2021-07-30 10:48:11
举报
文章被收录于专栏:算法与编程之美

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

引言

希尔排序(Shell Sort),是插入排序的一种又称“缩小增量排序”,同时它是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

问题描述

希尔排序是直接插入排序算法的一种更高效的改进版本。它是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

单从字面意思来理解,可能就有一点晦涩难懂,我们以一个例子来继续描述。

首先,发现它是一个10个数字组成的数组,初始增量为序号/2=5,于是之间的间隔为5。于是1号与6号比较,2号与7号比较……以此类推。

然后,二次增量为初始增量/2=2…1,于是二次增量为2,在初次结果的基础之上重新排序,1号与3、5、7、9号比较,2号与4、6、8、10号比较……以此类推。

三次增量为二次增量/2=1,则在二次结果的基础上进行排序,得出最终答案。

解决方案

在排序前,将一个序列分成了好几个序列,此外第一趟排序时:将这几个序列做插入排序。排序后,部分较大的数字往后靠,部分较小的数字往前靠,在第n趟排序时:将这个序列又分了好几个序列(直到剩下一个序列),从宏观上看,此序列就基本是有序的了。这时就用简单插入排序将数列直至已序。

结语

本文简单的介绍了典型的希尔排序,并以一个数组作为例子进行讲解。需要注意的是:希尔排序是基于插入排序的一种算法,希尔排序的时间复杂度为o()以此比时间复杂度为o()的要快许多。

实习编辑:李欣容

稿件来源:深度学习与文旅应用实验室(DLETA)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-07-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档