python实现插入排序

插入排序是一种简单直观的排序算法，其基本思想是把要排序的元素分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，插入到已排序的部分中，使得插入后仍然保持已排序部分的有序性。

以下是Python实现插入排序的代码：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

其中，参数`arr`是要排序的数组，`i`表示未排序部分的第一个元素，`key`表示要插入的元素，`j`表示已排序部分的最后一个元素。

在每一轮排序中，将`key`与已排序部分中的元素依次比较，找到插入位置后，将已排序部分中的元素后移，最后将`key`插入到该位置即可。

插入排序的时间复杂度为O(n^2)，在数据量较小的情况下，效率较高。