python 中的插入排序

插入排序是一种简单直观的排序算法，它的工作原理类似于整理扑克牌的过程。在Python中，插入排序通过迭代数组，将每个元素逐个比较并插入到已排序的部分，直到整个序列有序。

以下是插入排序的基本步骤：
1. 首先假设第一个元素已经排好序。
2. 从第二个元素开始，对于每一个元素（称为"当前元素"），找到其在已排序部分的正确位置。
3. 将当前元素移动到这个位置，可能需要将后续元素依次后移一位。
4. 重复这个过程，直到所有元素都被排序。

Python实现插入排序的一个例子：

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

# 示例
arr = [9, 7, 5, 11, 12]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)