希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap >= 1:
for j in range(1,n):
for i in range(j,0,-1):
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
else:
break
gap = gap // 2
return alist
if __name__ == '__main__':
li = [1, 3, 4, 2, 9, 5, 8]
print(li)
shell_sort(li)
print(li)
希尔排序是基于插入排序上的，因为插入排序每次一个一个数据的交换效率太低了，希尔排序是不稳定的
时间复杂度：最优O(n^^1.3)-->数据分析出来的，最坏O(n**2）
