希尔排序是插入排序的改进

• 先按一定的间隔将待排序的序列分组，每组进行插入排序
•     缩小间隔

      希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

def shell_sort(alist):if not alist:returnn=len(alist)gap=n//2while gap>0:for i in range(gap,n):while i>0:if alist[i]<alist[i-gap]:alist[i],alist[i-gap]=alist[i-gap],alist[i]i-=gapelse:breakgap//=2

复杂性：O(nlog(n))~O(n*n)

稳定性：不稳定