|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def shell_sort(arg): n = len(arg) gap = round(n/2) gap = int(gap) while gap > 0 : for i in range(gap,n): j = i while j > 0: if arg[j-gap] > arg[j]: arg[j-gap],arg[j]=arg[j],arg[j-gap] j = j-gap if gap == 1: break gap=round(gap/2) gap=int(gap) return arg |
代码参考地址：http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/#comments
另外一个动画演示
希尔排序本质还是进行的插入排序，只不过把原来的数组拆成多个小的数组
第一次的时候，可能虚拟机组只是每个组有2个数
5 1 2 3 4 6 9 7
5 4
1 6
2 9
3 7
这是因为gap是4
如果gap是2的时候
5 2 4 9
1 3 6 7
所以，最后gap=1的时候，就是一个完整的插入排序