python排序算法——希尔排序(附代码)
python排序算法——希尔排序
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。相比起初级排序算法,高级排序算法往往有更加复杂的逻辑,但也会有更高的时间或空间效率。其中有些高级排序算法是由初级排序算法优化而来的。
二、算法描述
希尔排序,又叫“缩小增量排序”,是对插入排序进行优化后产生的一种排序算法。它的执行思路是:把数组内的元素按下标增量分组,对每一组元素进行插入排序后,缩小增量并重复之前的步骤,直到增量到达1。
一般来说,希尔排序的时间复杂度为O(n1.3)~O(n2),它视增量大小而定。希尔排序的空间复杂度是O(1),它是一个不稳定的排序算法。进行希尔排序时,元素一次移动可能跨越多个元素,从而可能抵消多次移动,提高了效率。
下面是使用(数组长度/2)作为初始增量的升序希尔排序,每一轮排序过后,增量都缩小一半。第一步:如图2-28所示,从第一个元素开始,以增量4来分组。可以看出,当增量为4时,一组内只有两个元素,否则元素的下标就超出了数组的范围。
第二步:如图2-29所示,对组内的元素进行插入排序。
第三步:如图2-30所示,继续用相同的方法分组,对组内的元素进行插入排序使得它们有序。
整个数组内的数都被遍历完成后,这一轮排序就结束了。把增量缩小一半,继续进行下一轮排序。
第四步:如图2-31所示,增量为2时,可以看出每一组内的元素增多了,组的总数减少了。继续对每一组内的元素进行插入排序,直到每一组都遍历完成。
第五步:最后一轮排序如图2-32所示,再次把增量缩小一半;这时增量为1,相当于对整个数组进行插入排序,也就是最后一轮排序。
最后一轮排序结束后,整个希尔排序就结束了。
三、代码实现
在for循环中,由于每组的第一个元素不用进行插入排序,而它们的下标处于0~step-1,所以从下标step开始遍历。
需要注意的是,如果要模拟流程图中的做法,要使用两个循环:先分组,然后一次性使同组内的元素有序。为了提高效率,我们直接使用一个for循环,每遍历到一个数,就对它所在的组进行插入排序。这样遍历同样符合插入排序的顺序要求。在插入排序中,要改变当前下标的值,所以使用变量ind存储当前下标,防止影响for循环。
普通插入排序等同于增量为1的希尔排序,跨元素的希尔排序实际上只改变了增量,逻辑上与普通插入排序没有区别。
希尔排序代码:
nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
step = len(nums)//2 #初始化增量为数组长度的一半
while step > 0: #增量必须是大于0的整数
for i in range(step,len(nums)): #遍历需要进行插入排序的数
ind = i
while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
ind -= step
step //= 2 #增量缩小一半
print(nums)
ShellSort(nums)
运行程序,输出结果为:
[1,2,3,4,5,6,7,8]
总结
以上就是本文要讲的内容,本文介绍了希尔排序的理论知识和代码实现。一般来说,希尔排序的时间复杂度为O(n1.3)~O(n2),它视增量大小而定。希尔排序的空间复杂度是O(1),它是一个不稳定的排序算法。
相关文章
- EM算法求高斯混合模型參数预计——Python实现
- Python 集合(Set)、字典(Dictionary)
- 2年python编程自学经历(已工作),分享一些真实的学习心得和避坑经验
- Python 代码托管到码云平台,原来这么简单
- Python树莓派编程1.2.2 电源
- python实现归并排序算法
- 二叉搜索树-增删查Python
- 《Python算法教程》——1.5 本章小结
- 《Python算法教程》——第2章 基础知识 2.1 计算领域中一些核心理念
- 【21天学习经典算法】直接选择排序(附Python完整代码)
- 基于Python 实现直线段生成算法和圆弧生成算法【100010592】
- python 朴素算法
- Python机器学习算法备忘单之5 种常见算法的快速参考指南
- Python爬虫框架Scrapy
- Python实现下载文件的三种方法
- Python的参数模块OptionParser说明
- 华为OD机试 - 最长连续交替方波信号(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 通信误码(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 火星文计算(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 删除指定目录(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 推荐系统协同过滤-python实现(基于用户的协同过滤算法,基于物品的协同过滤算法,附数据集)
- 【机器学习】:Kmeans均值聚类算法原理(附带Python代码实现)
- 数据结构和算法:Python实现选择排序
- 【python】 实现冒泡排序及其优化
- 八大排序算法的Python实现