Python 插入排序实现的算法？

插入排序是一种简单的排序算法，它的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

def insertion_sort(arr):
    # 遍历从1到len(arr)
    for i in range(1, len(arr)):
        key = arr[i]

        # 将arr[0..i-1]中比arr[i]大的元素向后移动一位
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

# 测试代码
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print ("排序后的数组:")
for i in range(len(arr)):
    print ("%d" %arr[i]),

在这个实现中，我们首先假设数组的第一个元素已经排序（这是插入排序的一个基本假设，对于空数组或只有一个元素的数组，这个假设是成立的）。然后，我们从数组的第二个元素开始，将每个元素插入到已排序的部分中的正确位置。

为了找到正确的位置，我们将元素与已排序部分的每个元素进行比较，并将比它大的元素向后移动一位。当找到正确的位置时，我们将元素插入。

这个算法的时间复杂度是O(n^2)，其中n是数组的长度。这意味着，对于大型数据集，插入排序可能不是最有效的排序算法。然而，对于小型数据集或部分已排序的数据集，插入排序可能是非常有效的。