In [1]:
4,1,67,34,12,35,14,8,6,19
Out[1]:
(4, 1, 67, 34, 12, 35, 14, 8, 6, 19)
4 35
1 14
67 8
34 6
12 19需要注意的是，所谓的分组，仅仅是逻辑上的分组，这10个元素仍然在原来的序列中。 上面一共分了5组，每一组都进行插入排序，67 和 8 交换位置，34 和6 交换位置， 这样第一次分组后并对各组进行插入排序后，序列变成了
4, 1, 8, 6, 12, 35, 14, 67, 34, 194 8 12 14 34
1 6 35 67 19整个序列被分成了两组，分别对他们进行插入排序，排序后的结果为
4, 1, 8, 6, 12, 19, 14, 35, 34, 67In [1]:
lst = [4,1,67,34,12,35,14,8,6,19]
length = len(lst)
step = length//2
while step > 0:
for i in range(step):
# 插入排序
for j in range(i+step, length, step):
if lst[j] < lst[j-step]:
tmp = lst[j]
k = j-step
while k >= 0 and lst[k] > tmp:
lst[k+step] = lst[k]
k -= step
lst[k+step] = tmp
step //= 2 #缩小增量
print (lst)
[1, 4, 6, 8, 12, 14, 19, 34, 35, 67]