插入排序(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)。在列表基本有序的情况下,插入排序的性能可能更好。