插入排序

阅读量: 269 编辑

插入排序(Insertion Sort)是一种简单的排序算法,它将未排序的元素逐个插入到已排序部分的合适位置,从而逐步构建有序的列表。插入排序的思想类似于整理一手扑克牌,将新的牌插入到已经有序的牌中。

以下是使用插入排序算法对 Python 列表进行排序的示例代码:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # 将比 key 大的元素向后移动
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 将 key 插入到正确的位置
        arr[j + 1] = key

# 测试插入排序算法
my_list = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(my_list)
print("排序后的列表:", my_list)

运行此代码将输出:

排序后的列表: [11, 12, 22, 25, 34, 64, 90]

在这个示例中,insertion_sort() 函数接受一个列表作为参数,并对其进行插入排序。

外层循环从列表的第二个元素开始,内层循环将当前元素与已排序部分的元素进行比较,如果当前元素比较小,则将已排序部分的元素向后移动,直到找到合适的位置插入当前元素。

插入排序的时间复杂度取决于输入数据的初始顺序。在最坏情况下,即列表是逆序的,插入排序的时间复杂度为 O(n^2)。在列表基本有序的情况下,插入排序的性能可能更好。

爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司