谢尔排序—Python实现

谢尔排序

我们注意到插入排序的对比次数，在最好的情况下是O（n），这种情况发生在列表是已有序的情况下，实现上，列表越接近有序，插入排序的比对次数就越少。

对这个情况入手，谢尔排序以插入排序为基础，对无序表进行“间隔”划分子列表，每个子列表执行插入排序

间隔为3的子列表，子列表分别插入排序后的整体状况更接近有序

最后一趟是标准的插入排序，但由于前面几趟已经将列表处理到接近有序，这一趟仅需要少数几次移动即可完成

子列表的间隔一般从n/2开始，每趟倍增：n/4,n/8……直到1

代码

def shellSort(alist):sublistount=len(alist)//2while sublistount>0:for startposition in range(sublistount):gapInsertionSort(alist,startposition,sublistount)print("After increments of size",sublistount,"The list is",alist)sublistount=sublistount//2
def gapInsertionSort(alist,start,gap):for i in range(start+gap,len(alist),gap):current=alist[i]position=iwhile position>=gap and alist[position-gap]>current:alist[position]=alist[position-gap]position=position-gapalist[position]=currentalist=[52,312,54,7,3,2,56,34,65]
shellSort(alist)
print(alist)