个人技术博客地址：http://songmingyao.com/
原理
- 为插入排序的优化
- 对要排序的列表根据一定间隔（初始间隔一般设为列表长度的一半）进行分组
- 对各列表之间相同位置（下标）的元素进行插入排序
- 间隔减半，再次分组并对各列表之间相同位置（下标）的元素进行插入排序
- 如此循环，最终间隔为1，即为正常的插入排序
源码
def shell_sort(l):
n = len(l)
# 初始间隔
gap = n//2
while gap > 0:
for i in range(gap, n):
for j in range(i, gap-1, -gap):
if l[j] < l[j-gap]:
l[j], l[j-gap] = l[j-gap], l[j]
else:
break
gap //= 2
if __name__ == '__main__':
l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
print(l)
shell_sort(l)
print(l)
时间复杂度
- 最优时间复杂度（初始间隔为列表长度一半时）：O(nlogn)
- 最坏时间复杂度：O(n2)
- 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定
