如何用Python编写插入排序算法？

如何用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，并将排序后的结果返回。

在算法的主要循环中，我们从第二个元素开始，将其作为待插入元素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编写插入排序算法并不复杂。我们只需要理解插入排序的基本思想，然后根据思想实现相应的代码即可。当然，为了使代码更加健壮和通用，我们还可以对边界情况进行处理，例如空数组或只有一个元素的数组。

希望本文能对您理解和掌握插入排序算法有所帮助！