如何用Python编写插入排序算法？
插入排序是一种简单直观的排序算法，它的思想是将待排序的数组分为有序部分和无序部分，每次从无序部分中选择一个元素插入到有序部分的正确位置。插入排序算法的实现通常通过多次比较和交换元素来实现，时间复杂度为O(n^2)。
下面我们就来看一下用Python语言如何编写插入排序算法，以及具体的代码示例。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # 当前待插入元素
j = i - 1 # 有序部分的最后一个元素索引
# 将比key大的元素都向后移动一位
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 将key插入正确位置
return arr以上是插入排序算法的具体实现代码。在主函数中，我们需要传入一个待排序的数组arr，并将排序后的结果返回。
立即学习“Python免费学习笔记（深入）”；
在算法的主要循环中，我们从第二个元素开始，将其作为待插入元素key。然后，我们将key与有序部分的最后一个元素进行比较，将比key大的元素向后移动一位，直到找到key的正确位置。最后，我们将key插入到正确位置。
接下来，我们可以测试一下这个插入排序算法。
arr = [9, 5, 1, 6, 8, 2] sorted_arr = insertion_sort(arr) print(sorted_arr)
输出结果为：
[1, 2, 5, 6, 8, 9]
可以看到，通过插入排序算法，我们成功地将输入的数组按照升序排列。
总结起来，使用Python编写插入排序算法并不复杂。我们只需要理解插入排序的基本思想，然后根据思想实现相应的代码即可。当然，为了使代码更加健壮和通用，我们还可以对边界情况进行处理，例如空数组或只有一个元素的数组。
希望本文能对您理解和掌握插入排序算法有所帮助！
