最简单的插入排序算法代码

插入排序是一种简单直观的排序算法，它的工作原理就像打扑克牌一样。以下是使用Python编写的最简单的插入排序算法代码：

def insertion_sort(arr):
    # 遍历从1到n的所有元素
    for i in range(1, len(arr)):
        key = arr[i]  # 当前元素
        j = i - 1  # 指向已排序部分的最后一个元素

        # 将key（当前元素）逐个比较并插入到已排序数组的正确位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # 将较大的元素向右移动一位
            j -= 1  # 移动索引向前查找

        arr[j + 1] = key  # 插入到正确的位置
    return arr

# 测试代码
arr = [4, 2, 8, 5, 9]
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)