基本思想
由于插入排序在最坏的情况下时间复杂度为O(n的平方)，在最好的情况下时间复杂度为O(n)，如果对待排序元素按关键字基本有序，插入排序的效率将大大提高，显然当元素个数n较少时效率也比较高，shell排序就是从这两方面对插入排序进行改进的。
先将整个待排序序列分割成若干子序列，分别对各个子序列进行直接插入排序，等整个序列中的数据元素“基本有序”是，再对全体数据元素进行一次直接插入排序。
来自百度百科.png
python实现
#!/usr/bin/python
# encoding: utf-8
# 希尔排序
def shellSort(alist):
# 设定步长
step = len(alist) // 2
while step > 0:
# 对step到最后一个位置都进行插入排序
for i in range(step, len(alist)):
tmp = alist[i]
j = i
while j >= step and tmp < alist[j - step]:
# 如果前面的数比tmp小，就往后移
alist[j] = alist[j-step]
# 每次都是按照step长度往前移动
j -= step
alist[j] = tmp
# 更新步长
step = step // 2
if __name__ == '__main__':
a = [4, 1, 3, 7, 5, 2, 9, 6, 8,11,10]
shellSort(a)
print(a) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
