- 谢尔排序以插入排序作为基础
- 子列表的间隔一般从n/2开始
- 大致介于O(n)和O(n^2)之间,如果将间隔保持在 (1,3,5,7,15,31等等),谢尔排序的时间复杂度约为O( )
def shellSort(alist): sublistcount = len(alist)//2 #间隔设定 while sublistcount > 0: #子列表排序 for startposition in range(sublistcount): gapInsertionSort(alist,startposition,sublistcount) print('After increments of size',sublistcount,'The list is',alist) sublistcount = sublistcount // 2 #间隔缩小 def gapInsertionSort(alist,start,gap): for i in range(start+gap, len(alist), gap): currentvalue = alist[i] position = i while position >= gap and alist[position-gap] > currentvalue: alist[position] = alist[position - gap] position = position - gap alist[position] = currentvalue