插入排序的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

在这个实现中，我们首先遍历待排序数组，从第二个元素开始（因为第一个元素默认已经是有序的）。然后我们将当前元素存储在变量key中，并将其与已排序的序列进行比较。如果已排序序列中的元素大于key，则将该元素向右移动一位，直到找到一个小于或等于key的元素。最后，我们将key插入到该位置，并继续遍历数组，直到所有元素都被插入到已排序序列中。