Python数据结构与算法(15)---希尔排序

简介: Python数据结构与算法(15)---希尔排序

希尔排序


希尔排序,又称作Shell Sort,也叫缩小增量排序算法,是前文讲解的插入排序更高效的一种排序算法。


其原理是:在n个元素的列表里,取增量n/2。数列开始值与增量值的尾值进行比较,小的放前面,大的放后面;把增量的前后都比较一遍,然后增量数-1。


继续从头到尾进行比较,并调整大小;一直到增量等于1,就完成了所有列表元素的排序。至于增量规则可以自行定义。


图解写入排序

假设,又一个列表为[8,0,4,3,2,1]。具体原理步骤如下:


第1次,增量为3,那么需要进行3次循环。(每次循环2个数进行比较排序)


上面,首先对索引0到索引3的数值进行比较,然后比较索引1与索引4,最后比较索引2与索引5的值。


第2次,增量为2,那么需要进行2次循环。


接着,对索引0、索引2、与索引4的数值进行比较,然后比较索引1、索引3、索引5的数值。


第3次,增量为1,那么需要进行1次循环。


最后,对比索引0与索引1,索引1与索引2,索引2与索引3,索引3与索引4,索引4与索引5的各个数的值。就完成了最终的排序过程。这个过程就叫希尔排序。


实战:希尔排序

通过上面的举例,以及图解的分析,相信读者都能够看懂希尔排序的过程以及相对应的原理。下面,我们来用Python实现希尔排序,示例如下:

def shell_sort(my_list):
    n = len(my_list)
    if n == 1:
        return my_list
    space = int(n / 2)
    while space > 0:
        for i in range(space, n):
            temp = my_list[i]
            j = i
            while j >= space and my_list[j - space] > temp:
                my_list[j] = my_list[j - space]
                j -= space
            my_list[j] = temp
        space = int(space / 2)
    return my_list
if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("排序前的数组:", my_list)
    print("排序后的数组:", shell_sort(my_list))

运行之后,效果如下所示:


相关文章
|
17天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
195 55
|
6天前
|
存储 缓存 监控
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
96 66
|
2月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
137 67
|
2月前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
128 61
|
27天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
145 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
10天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
46 20
|
2天前
|
算法 网络协议 Python
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。
|
7天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
37 5
|
7天前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
41 0
|
算法 搜索推荐 Python
python实现希尔排序算法
希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1329 0