本文主要是介绍【数据结构与算法python】谢尔排序算法的python实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1、概念解释
我们注意到插入排序的比对次数, 在最好的情况下是O(n), 这种情况发生在列表已是有序的情况下, 实际上, 列表越接近有序, 插入排序的比对次数就越少。 从这个情况入手, 谢尔排序以插入排序作为基础, 对无序表进行“间隔”划分子列表, 每个子列表都执行插入排序。
随着子列表的数量越来越少, 无序表的整体越来越接近有序, 从而减少整体排序的比对次数,以间隔等于3为例,子列表分别插入排序后的整体状况更接近有序
最后一趟是标准的插入排序, 但由于前面几趟已经将列表处理到接近有序, 这一趟仅需少数几次移动即可完成
子列表的间隔一般从n/2开始, 每趟倍增: n/4, n/8……直到1
2、代码实现
def shellSort(alist):sublistcount = len(alist)//2while sublistcount > 0:for startposition in range(sublistcount):gapInsertionSort(alist,startposition,sublistcount)print("After increments of size",sublistcount,"The list is",alist)sublistcount = sublistcount // 2def gapInsertionSort(alist,start,gap):for i in range(start+gap,len(alist),gap):currentvalue = alist[i]position = iwhile position>=gap and alist[position-gap]>currentvalue:alist[position]=alist[position-gap] position = position-gapalist[position]=currentvaluealist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)
3、算法分析
谢尔排序以插入排序为基础,可能并不会比插入排序好,但由于每趟都使得列表更加接近有序, 这过程会减少很多原先需要的“无效”比对对谢尔排序的详尽分析比较复杂,大致说是介于O(n)和O(n2)之间。如果将间隔保持在2k-1(1、 3、 5、 7、 15、 31等等) , 谢尔排序的时间复杂度约为O(n3/2) 。
这篇关于【数据结构与算法python】谢尔排序算法的python实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!