python笔试面试项目实战2020百练5插入排序希尔排序

插入排序

插⼊排序 的时间复杂度也是 ，但原理稍有不同。它在列表较低的⼀端维护⼀个有序的⼦列表，并逐个将每个新元素“插⼊”这个⼦列。

图片.png

def insertion_sort(items):
    for index in range(1,len(items)):
        currentvalue = items[index]
        position = index
        while position>0 and items[position-1] > currentvalue:
            items[position] = items[position-1]
            position = position-1

        items[position] = currentvalue

items = [54,26,93,17,77,31,44,55,20]
insertion_sort(items)
print(items)

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• python工具书籍下载-持续更新
• 本文配套视频在线播放 下载

希尔排序

希尔排序 也称“递减增量排序”，它对插⼊排序做了改进，将列表分成数个⼦列表，并对每⼀个⼦列表应⽤插⼊排序。如何切分列表是希尔排序的关键——并不是连续切分，⽽是使⽤增量 （有时称作步⻓ ）选取所有间隔为 的元素组成⼦列表。

下图这个列表有9个元素。如果增量为3，就有3个⼦列表，每个都可以应⽤插⼊排序。尽管列表仍然不算完全有序，但通过给⼦列表排序，我们已经让元素离它们的最终位置更近了。

def shell_sort(items):
    sublistcount = len(items)//2
    while sublistcount > 0:
        for start in range(sublistcount):
            gap_insertion_sort(items,start,sublistcount)
        print("After increments of size",sublistcount,"The list is",items)
        sublistcount = sublistcount // 2

def gap_insertion_sort(items,start,gap):
    for i in range(start+gap,len(items),gap):
        currentvalue = items[i]
        position = i
        while position >= gap and items[position-gap] > currentvalue:
            items[position] = items[position-gap]
            position = position-gap

        items[position] = currentvalue

items = [54,26,93,17,77,31,44,55,20]
shell_sort(items)
print(items)