导语:
本文主要介绍了关于python中如何进行希尔排序?的相关知识,包括python做界面,以及在python中这些编程知识,希望对大家有参考作用。
如果问大家拿来做科学计算,那属于插入排序的收缩增量法是什么?你知道吗?其实就是希尔排序法。 Shell排序是Donald Shell于1959年提出的一种排序算法。Hill排序也是一种插入排序,是一种将整个非序列分成若干小的子序列进行插入排序的方法。它是简单插入排序的更高效版本,也称为收缩增量排序,该算法是最早突破 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中实现加密12/23
- ♥ 如何用 Python 替换文件的内容?10/26
- ♥ 如何在终端中运行python10/12
- ♥ python的功能是什么08/12
- ♥ 如何下载安装python3.608/30
- ♥ 什么是python检查功能09/04
内容反馈