数据结构---希尔排序
希尔排序。
终于在此刻将这个排序学完了。。这个排序讲什么的呢?
就是说,它对一个序列,取了一个gap的步长。然后呢,用gap将这个序列分成了很多组,然后就是每组进行插入排序(插入排序:将一个序列从前往后走,每走一步,就将这个元素和它前面的所有元素比较交换位置。)。
下面上代码:
def shell_sort(alist):
n = len(alist) # 找到整个序列的长度
gap = n // 2 # 首先选出整个序列的gap,取中间值
while gap > 0: # 这时候我们的gap需要进行遍历,每次取半
for j in range(gap,n): # 从gap到n我们都要每个元素都要比较
i = j
while i > 0: # 这里是为了给每个gap分组后的序列排序时准备的终止条件
if alist[i] < alist[i-gap]: # 如果后者比前者小,就要交换位置
alist[i],alist[i-gap] = alist[i-gap],alist[i] # 交换位置
i -= gap # 每次交换完位置之后,就要往前移动gap的间隔进行再次比较
else: # 如果当前位置的值比前者大,不需要移动,就直接结束这次判断
break
gap = gap // 2 # 遍历gap时候每次都取半
希尔排序
- 最优时间复杂度:根据选择步长不同而不同
- 最坏时间复杂度:O(n2)
- 稳定性: 不稳定