【python 谢尔排序算法】

算法基本原理思想

注意到插入排序的比对次数，在最好的情况下是0（n），这种情况发生在列表已是有序的情况下，实际上，列表越接近有序，插入排序的比对次数就越少；从这个情况入手，谢尔排序以插入排序作为基础，对无序表进行“间隔”划分子列表，每个子列表都执行插入排序。

• 随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数

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

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

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

简单排序代码示例

'''
@ time ：2021年10月22日
@ author ： wupke
@ description: 谢尔排序算法
'''import time# # #    
start1 = time.clock()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//2# 插入排序
def gapInsertionSort(alist,start,gap):for  i in range(start+gap, len(alist),gap):# gap 是步长，新插入项currentvalue = alist[i]position = iwhile position >= gap and alist[position-gap]>currentvalue:# 对比，移动alist[position] = alist[position-gap]position = position-gap#插入新项alist[position]=currentvaluealist = [22,33,44,55,21,31,45,76,88,54,3,5,7,2]
shellSort(alist)
end1 = time.clock()
print("%s排序用时%s" %(alist,(end1-start1)))

复杂度分析

• 粗看上去，谢尔排序以插入排序为基础，可能并不会比插入排序好
• 但由于每趟都使得列表更加接近有序，这过程会减少很多原先需要的“无效”比对对谢尔排序的详尽分析比较复杂，大致说是介于0（n）和0（n2）之间。