python 排序算法——希尔排序

# 数据结构与算法
# 排序算法 ———— 希尔算法

# 比较性：排序时元素之间需要比较，所以为比较排序
#
# 稳定性：因为希尔排序是间隔的插入，所以存在相同元素相对顺序被打乱，
# 所以是不稳定排序
#
# 时间复杂度：   最坏时间复杂度O(n^2)平均复杂度为O(n^1.3)
#
# 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
#
# 记忆方法：插入排序是每轮都是一小步，希尔排序是先大步后小步，
# 它第一个突破O(n2)的排序算法。联想起阿姆斯特朗登月之后说：
# 这是我个人一小步，却是人类迈出的一大步。
#

def shell_sort(alist):
	n = len(alist)
	gap = n//2
	while gap >0 :
#		for j in range(gap,n):
#			while j > 0 :
#				if alist[j] < alist[j-gap]:
#					alist[j], alist[j-gap] = alist[j-gap], alist[j]
#					j -= gap
#				else:
#					break
		for i in range(gap,n):
			for j in range(i,0,-gap):
				if alist[j] < alist[j-gap]:
					alist[j], alist[j-gap] = alist[j-gap], alist[j]
				else:
					break
		gap //= 2
lis = [3,2,5,7,2,8,8,3,44,75,3]
shell_sort(lis)
print(lis)