导航：首页 > 互联网科技 >

如何使用python实现插入排序算法

发表于：2025-02-02 作者：千家信息网编辑

千家信息网最后更新 2025年02月02日，小编给大家分享一下如何使用python实现插入排序算法，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！插入排序通俗理解：插入排序是从数组中取出一个元素与其前面的一个或多个元素进行逐一比

千家信息网最后更新 2025年02月02日如何使用python实现插入排序算法

小编给大家分享一下如何使用python实现插入排序算法，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

插入排序通俗理解：插入排序是从数组中取出一个元素与其前面的一个或多个元素进行逐一比较，依照大小将其插入到合适的位置。要注意区分和选择排序的差别：选择排序排序之选择排序和插入排序实际上是人为地把数组切分为前后两半部分，选择排序中前半部分的元素始终是排序好的，逐个拿后半部分的每一个元素与后半部分数组中'0'索引位置的元素比较大小交换位置，而插入排序是在每次遍历数组的时候，在后半部分数组元素中取一个元素，与前半部分的元素逐个比较，比某个元素大，则放在其后面，比某个元素小，则放在其前面，这里比某个值大或者小是通过一次一次地往前走而比较出来的。如果觉得上述描述不甚清晰，下面的示例可帮助进一步理解：

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 alist

if __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实现插入排序算法"有了一定的了解，如果想了解更多相关知识，欢迎关注行业资讯频道，感谢各位的阅读！

很赞哦！