希尔排序
希尔排序的思想
希尔排序是对插入排序的一种改进方法，它把原来的列表分成无数个子列表，然后对每个子列表来执行插入排序，希尔排序的关键就在于对步长的控制（可以看作是每间隔几个元素取元素作为子列表）。
图解希尔排序
给定如下的列表：
我们使用2作为步长（每隔两个字符取一个元素），可以划分成如下的三个子列表。
有了三个子列表之后，我们分别对三个子列表进行插入排序
根据上图可以发现我们得到的组合结果并没有完全排序成功，最后我们还需要对这个列表进行一次插入排序。
这样我们的希尔排序就完成了。
希尔排序的性质
- 最优时间复杂度：$O(n)$
- 最坏时间复杂度：$O(n^2)$
- 稳定性：不稳定
- 对比插入排序：通过改变增量会优化时间复杂度。
希尔排序的代码实现
lst = list(map(int, input().split(',')))
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap, n):
j = i
while j >= gap:
if alist[j] < alist[j - gap]:
alist[j], alist[j - gap] = alist[j - gap], alist[j]
j -= gap
else:
break
gap //= 2
return alist
shell_sort(lst)