本文主要是介绍谢尔排序—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)
这篇关于谢尔排序—Python实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!