插入排序算法（Insertion Sort）

# /*
# 插入排序算法（Insertion Sort）
# --------------------------------------------------------
# 原理：
# 将数据分为“已排序区”和“未排序区”。
# 每次从未排序区取一个元素，插入到已排序区的正确位置。
#
# 类似整理扑克牌：手中的牌是已排序区，新摸到的牌插入到合适位置。
# */

def insertion_sort(arr):
    # 从第 1 个元素开始，因为第 0 个元素默认已经“排序好”
    for i in range(1, len(arr)):
        key = arr[i]           # 当前要插入的元素
        j = i - 1              # 从已排序区的末尾开始比较

        # 若已排序区的元素 > key，则将其向右移
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 将 key 放到正确位置
        arr[j + 1] = key

    return arr


# 示例演示
data = [12, 11, 13, 5, 6]
print("排序前：", data)
sorted_data = insertion_sort(data)
print("排序后：", sorted_data)

# --------------------------------------------------------
# 关键要点总结：
# 1) 插入排序稳定（不会改变相同元素相对顺序）
# 2) 最佳情况（已排好序）时间复杂度 O(n)
# 3) 最坏情况（逆序）时间复杂度 O(n²)
# 4) 实现简单，适用于数据量小或部分有序的情况
# */

# 排序前： [12, 11, 13, 5, 6]
# 排序后： [5, 6, 11, 12, 13]