python中如何进行希尔排序?
2023-03-20 15:25:42 时间
如果问大家用于科学计算,属于插入类排序的缩小增量法是什么?你知道吗?其实是希尔排序法。 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。本文会向大家向大家介绍python中的希尔排序及其使用代码。
希尔排序
背景:插入排序在小规模数据、数据基本有序时效率较高
思想:将序列分为若干子序列进行插入排序,待序列基本有序时,对整体进行插入排序
代码:
# python实现希尔排序(插入排序的一种) # 先宏观进行调整,在进行微观调整 def shellSort(lst, k, reverse=False): length = len(lst) dk = k # 设置一个增量dk while dk > 0: for i in range(dk, length): temp = lst[i] j = i while j >= dk and lst[j - dk] > temp: lst[j] = lst[j - dk] j -= dk lst[j] = temp dk = int(dk / 2) if reverse == False: return lst else: lst.reverse() return lst
输出:
test1 = [19, 21, 4, 6, 25, 3, 99, 67, 12] test2 = [19, 21, 4, 6, 25, 3, 99, 67, 12] data1 = shellSort(test1, 7) data2 = shellSort(test2, 2, True) print("从小到大:", data1) print("从大到小:", data2)
希尔排序在最优时间复杂会根据步长序列的不同而不同,最坏时间复杂度是O(n^2),在操作过程中是不稳定的,要注意哦~
相关文章
- Python中的函数与方法 以及Bound Method和Unbound Method
- 一文贯通python文件读取
- Python 中的异步编程:Asyncio
- 7个你现在就该学习Python的理由
- 提高Python运行效率的六个窍门
- Python数据科学:神经网络
- 一篇文章看懂大数据分析就业前景及职能定位
- R和Python中的文本挖掘:8个入门小贴士
- 告诉你为什么Python有点慢,但我却无所谓?
- 专注学习DevOps编程语言Top 5推荐
- Python发送邮件脚本
- Python多进程并行编程实践: mpi4py 的使用
- Python语言在未来的发展前景
- Python vs Ruby: 谁是最好的 web 开发语言?
- Python对Ruby:谁在Web开发领域更胜一筹?
- Python一行代码完成并行任务
- Python开发者2017应该关注的七个类库
- python爬虫入门基本知识
- 在终端中优雅地编写Python
- Python机器学习实战:信用卡欺诈检测