python中如何进行希尔排序？

如果问大家用于科学计算，属于插入类排序的缩小增量法是什么？你知道吗？其实是希尔排序法。希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会向大家向大家介绍python中的希尔排序及其使用代码。

背景：插入排序在小规模数据、数据基本有序时效率较高

思想：将序列分为若干子序列进行插入排序，待序列基本有序时，对整体进行插入排序

代码：

#python实现希尔排序(插入排序的一种)
#先宏观进行调整，在进行微观调整

defshellSort(lst,k,reverse=False):
length=len(lst)
dk=k#设置一个增量dk
whiledk>0:
foriinrange(dk,length):
temp=lst[i]
j=i
whilej>=dkandlst[j-dk]>temp:
lst[j]=lst[j-dk]
j-=dk
lst[j]=temp
dk=int(dk/2)
ifreverse==False:
returnlst
else:
lst.reverse()
returnlst

输出：

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)，在操作过程中是不稳定的，要注意哦~