Python实现插入排序算法

插入排序（Insertion Sort）是一种简单的排序算法，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置并插入。插入排序比较适合于小规模数据的排序，时间复杂度为O(n^2)。

下面是 Python 实现插入排序算法的代码演示：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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 = [5, 2, 9, 1, 5, 6]
print(insertion_sort(arr))

# 输出：[1, 2, 5, 5, 6, 9]

在这个示例中，当 i=1 时，我们将 key 的值设置为 arr[1]，即 2。然后将 j 设置为 0，并检查 arr[j] 是否大于 key。由于 arr[j] = 5 > key = 2，我们将 arr[j+1] 的值设置为 arr[j]，即将 2 插入到正确的位置。这样，我们就完成了一次迭代。

在下一次迭代中，当 i=2 时，我们将 key 的值设置为 arr[2]，即 9。我们将 j 设置为 1 之后发现 arr[j] < key，因此不需要移动 arr[j]。然后，我们将 arr[j+1] 的值设置为 key，即将 9 插入到正确的位置。

这个过程会一直重复，直到我们遍历了整个数组。最终，我们得到一个升序排列的数组。