小编给大家分享一下如何使用python实现插入排序算法，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！
def insert_sort(alist):'''插入排序'''length = len(alist)# 默认第一个元素不动，从索引为1的元素开始与前面元素比较for i in range(1,length):print(i)for j in range(i,0,-1): # 倒叙逐一取range中的值if alist[j] < alist[j-1]:alist[j-1],alist[j] = alist[j],alist[j-1]# 输出此次比较后的数组print(alist)return alistif __name__ == '__main__':alist = [3,2,1,7,6,5,3]print(insert_sort(alist))
代码流程：首先获取列表长度，外for循环循环次数为列表长度减1，内循环理论上每次循环的次数是逐一增加的，因为前半部分数组中的元素每经过一次完全的遍历就多一个，而后半部分恰恰相反，每次减少一个。下面通过结果来看看具体是怎么实现的：
1 #第一次结果[2, 3, 1, 7, 6, 5, 3]2 #第二次结果[1, 2, 3, 7, 6, 5, 3]3 #第三次结果[1, 2, 3, 7, 6, 5, 3]4 #第四次结果[1, 2, 3, 6, 7, 5, 3]5 #第五次结果[1, 2, 3, 5, 6, 7, 3]6 #第六次结果[1, 2, 3, 3, 5, 6, 7]# 最终结果[1, 2, 3, 3, 5, 6, 7]
结果分析：当第一轮遍历时，原数组alist[3,2,1,7,6,5,3]中的1索引值为2，与0索引的值3进行比较，小于则进行交换，得到此次的最终结果[2, 3, 1, 7, 6, 5, 3]；第二次遍历，2索引的值1小于1索引的值3，交换得到[2, 1, 3, 7, 6, 5, 3]，现在还没有结束，因为内for循环的循环列表为[2,1,-1]，接着1索引的值1小于0索引的值2，进行交换，此时才得到此轮的最终结果[1, 2, 3, 7, 6, 5, 3]，以此类推可实现最终排序。
复杂度：插入排序复杂度为n**2，其最好最坏均为n方，无论原始数组是否有序，总要拿着后面的每一个元素与其前面的所有元素逐一比较大小，因为你不能保证所取的元素比其前面的每个元素都小。
看完了这篇文章，相信你对“如何使用python实现插入排序算法”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
