插入排序

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

图片.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] = currentvalueitems = [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 // 2def 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] = currentvalueitems = [54,26,93,17,77,31,44,55,20]shell_sort(items)print(items)

原著是一个有趣的人,若有侵权,请通知删除