def insertion_sort(arr):
    """
    插入排序算法实现
    参数:
        arr (list): 待排序的列表
    返回:
        list: 排序后的列表
    """
    # 遍历从1到len(arr)-1
    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
        
        # 将key插入到正确位置
        arr[j + 1] = key
    
    return arr

# 测试插入排序
if __name__ == "__main__":
    data = [9, 5, 1, 4, 3, 7, 8, 2, 6]
    print("原始数组:", data)
    sorted_data = insertion_sort(data.copy())
    print("排序后数组:", sorted_data)

代码说明

• 外层循环：从索引1开始遍历到数组末尾，表示未排序部分的开始
• key变量：存储当前需要插入的元素值
• 内层循环：将当前元素与已排序部分比较，找到合适的插入位置
• 移动元素：将比key大的元素向右移动，为key腾出插入空间
• 插入操作：当找到合适位置后，将key插入该位置

与其他排序算法比较

插入排序是一种简单但高效的算法，特别适用于小规模数据或基本有序的数据集。虽然其时间复杂度为O(n²)，不适合大规模数据排序，但在特定场景下它比许多O(n log n)的算法更高效。

在实际应用中，插入排序常被用作更高级算法（如TimSort）的子过程，用于处理小型数组。理解插入排序有助于掌握更复杂的排序算法，是算法学习的重要基础。