希尔排序原理：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，最后在基本有序后最后做一次直接插入排序。
时间复杂度：O(nlogn) 最坏是O(n ** s)(1<s<2) 不稳定的排序方法；
空间复杂度：O(1)
#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Thu Jul 18 03:42:18 2019 @author: honorwh """ #希尔排序 def ShellSort(A): count = len(A) step = count // 2 while step > 0: for i in range(0, step): j = i + step while j < count: k = j - step key = A[j] while k >= 0: if A[k] > key: A[k + step] = A[k] A[k] = key k -= step j += step step //= 2 return A A = [3, 4, 2, 8, 9, 5, 1] A = ShellSort(A) print(A)希尔排序有个重点是对于增量（increment）的选择，这里选择是step = len(A) // 2, step //= 2
结合以上图片给出每一步的数值转移：
A = [3, 4, 2, 8, 9, 5, 1]
3 4 2 8 9 5 1(以step = len(A) // 2为步长) 第一次比较的是3 8；8 1; 3 1
即3 4 2 8 9 5 1 --> 3 4 2 1 9 5 8 --> 1 4 2 3 9 5 8
所以，1 4 2 3 9 5 8是第一次比较的结果；同理，在以step = len(A) // 2的步长比较之后，step //= 2
即第二次（在本例已经是最后一次，因为step = 1），所以同理即可得到结果。
这个编辑比较麻烦，有兴趣可以自己每一步的详细过程推一推，更容易理解。
