一文掌握Python 中的排序算法——插入排序

Python 中的插入排序是一种简单的排序算法，可用于对任何线性数据结构（如列表）进行排序。仅次于气泡排序，非常接近人类手动排序的方式（例如扑克牌）。顾名思义，插入排序就是在排序列表中插入元素。

当我们每次打牌时，我们都会拿一张新牌并插入到适当的位置，这就是一种插入排序。

在插入排序技术中，我们从第二个元素开始。然后将其与第一个元素进行比较，并将其放在适当的位置。然后对后续元素执行此过程。

可以使用如下所示的动画了解 Python 中的插入排序的工作原理。

原始数据：[6,5,3,1,8,7,2,4]
第一次迭代：[5,6,3,1,8,7,2,4] 
第二次迭代：[3,5,6,1,8,7,2,4]
第三次迭代：[1,3,5,6,8,7,2,4]
第四次迭代：[1,3,5,6,8,7,2,4]
第五次迭代：[1,3,5,6,7,8,2,4]
第六次迭代：[1,2,3,5,6,7,8,4]
第七次迭代：[1,2,3,4,5,6,7,8]

排序方式：升序排列

假设第一个数字 6 已完成排序。

第一次迭代，从数字 5 开始迭代。与前面的数字 6 比较，不符合排序要求，交换数字 5 和数字 6 的位置，即，将数字 5 插入到 数字 6 前面。

第二次迭代，数字 3 与前面的数字 6 比较，不符合排序要求，交换位置。继续与前面的数字 5 比较，不符合排序要求，交换位置。

按照此过程继续迭代下一个元素，直到完成排序。

「程序代码：」

def insertion_sort(lst):
    for i in range(1, len(lst)):
        for j in range(i - 1, -1, -1):
            if(lst[j] > lst[j + 1]):
                lst[j], lst[j + 1] = lst[j + 1], lst[j]                
list1 = [6,5,3,1,8,7,2,4]
insertion_sort(list1)
print(f"排序结果：{list1}")

我们看到插入排序与现实生活中的排序方式非常相似，如果排序数据个数加倍，则执行所需的时间增加四倍，如果数量增加三倍，则执行所需的时间增加九倍。这使得插入排序在实际使用中效率低下，但它是一种非常直观的算法。

?

文章创作不易，如果您喜欢这篇文章，请关注、点赞并分享给朋友。如有意见和建议，请在评论中反馈！

?