如何使用Python函数实现插入排序算法？

插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列分为已排序和未排序两部分，每次将未排序的元素插入到已排序的合适位置，从而逐步构建有序序列。

下面是使用Python函数实现插入排序算法的代码：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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

    return arr

在这段代码中，arr代表待排序的序列，n表示序列的长度。我们使用一个for循环遍历待排序序列，从第二个元素开始，将其与已排序序列中的元素进行比较。

在内部的while循环中，我们逐个比较已排序序列中的元素与当前元素key的大小，如果已排序序列中的元素大于key，则将该元素右移一位，直到遇到一个小于等于key的元素或者已经遍历完已排序序列。最终，将key插入到合适的位置。

最后，返回排好序的序列arr。

可以使用以下代码测试该插入排序算法：

arr = [5, 2, 8, 12, 7]
sorted_arr = insertion_sort(arr)
print(sorted_arr)  # 输出 [2, 5, 7, 8, 12]

上述代码中，我们将输入序列[5, 2, 8, 12, 7]作为参数传递给insertion_sort函数，并打印出排序结果。

插入排序算法的时间复杂度为O(n^2)，适用于小规模或几乎已排序的列表。在实际应用中，通常不推荐使用插入排序算法来排序大规模的数据。