【python & 谢尔排序算法】

【python & 谢尔排序算法】

【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)//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):
        # 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
        
alist = [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）之间。