建议先点击查看 插入法 ，再看希尔排序。这个算法大致思路是：
基本思想是：先比较距离远的元素，而不是像简单交换排序算法那样先比较相邻的元素，这样可以快速减少大量的无序情况，从而减轻后续的工作。被比较的元素之间的距离逐步减少，直到减少为1，这时的排序变成了相邻元素的互换。
可以先看看这个趣味演示视频再看代码：
http://v.youku.com/v_show/id_XNTA3NDUxMjcy.html
代码如下：
# 以下是插入法，两者做个对比：
def insert_sort(lst):
for i in range(1, len(lst)):
if lst[i-1] > lst[i]:
index = i
temp = lst[i]
while lst[index-1] > temp and index > 0:
lst[index] = lst[index - 1]
index -= 1
lst[index] = temp
return lst
# 这才是希尔排序
def shell_sort(lis):
n = len(lis)
gap = n // 2
while gap > 0:
for i in range(gap, n):
index = i
temp = lis[i]
while lis[index - gap] > temp and index >= gap:
lis[index] = lis[index - gap]
index -= gap
lis[index] = temp
gap = gap // 2
return lis
核心的区别在于， insert 的步长始终是 1，而 shell 的步长是从大变小直到为1。insert 总是相邻的 2 个元素比较，而 shell 是较远的两个元素比较。
步长（gap）的选择会导致算法复杂度不同，我们就用 n/2 来。也就是每次步长减半，最后为 1。最坏情况的算法复杂度是 O(n^2)。
这个代码是很难现推的，也不建议现推。背下来好点。
记住大的框架是 while for while。
# 来一起背一遍。
def shell_sort(lst):
n = len(lst)
gap = n//2
while gap > 0:
# 以上三行死背。
for i in range(gap, n):
index = i
temp = lst[i]
# 以上理解成把当前项拎出来。
while temp < lst[index - gap] and index >= gap:
# 当前项比前一个项小才交换位置。并需要确保序号 index - gap >= 0，由此得到第二个条件。
lst[index] = lst[index - gap]
# 前一项的值覆盖掉当前项。
index -= gap
# 只要还在 while 循环，那么就继续和更靠前的项比较并把值覆盖给后一项。
lst[index] = temp
# 最后跳出 while ，说明 index = 0 或者 temp 大于前项。
# 注意不是赋给 lst[index-gap]，因为出循环的时候 index -= gap 了。
gap = gap//2 - 1
return lst
一定要注意第二个 while 循环中，是拿拎出来的 temp 一个个和间隔 gap 的元素比较，然后插入。因此不要写错 lst[index]。
还有 gap 最好不要 8，4，2，1这样，因为数字不互质，建议 gap = gap//2 -1 。
具体例子可以参考：
https://www.bilibili.com/video/av15961896?from=search&seid=14094459639601474645
从 05:45 开始。
