当前位置: 首页 > >

经典排序算法-希尔排序-python实现

发布时间:

?


希尔排序(shell sort)又称为缩小增量排序,是1959年D?L?Shell提出来的。是插入排序的改进版


基本思想是:设待排序元素序列有n个元素,首先取一个整数jump(小于n)作为间隔将全部元素分为jump个子序列,所有距离为jump的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔jump,重复上述子序列划分和排序工作。直到最后取jump=1,将所有元素放在同一个子序列中排序为止。?
由于开始时,jump的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期jump取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。?

def ShellSort(s):
jump = len(s)//2
while jump != 0:
for i in range(jump,len(s)):
temp = s[i]
j = i - jump
if temp= 0:
s[j+jump]=s[j]
j = j -jump
s[j+jump]=temp
jump=jump//2
print(s)
return s


s=[5,99,7,55,85,24,45,36]
print(s)
ShellSort(s)
print(s)

?



友情链接: