插入排序是一种简单直观的排序方法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种算法类似于我们在打扑克牌时整理手中牌的过程，每次将一张牌插入到其他已经排好的牌中的适当位置。
其核心思想是把数组分成两部分：
已排序部分（左边，初始只有第一个元素）
未排序部分（右边，剩下所有元素）
然后逐个取出未排序部分的元素，把它插入到已排序部分的正确位置，直到整个数组有序。
以数组 [5, 2, 4, 6, 1, 3] 为例，一步步看：
初始：已排序 = [5]，未排序 = [2,4,6,1,3]
取 2 → 插入到 5 前面 → 已排序 = [2,5]
取 4 → 插入到 2 和 5 之间 → 已排序 = [2,4,5]
取 6 → 放在最后 → 已排序 = [2,4,5,6]
取 1 → 插入到最前面 → 已排序 = [1,2,4,5,6]
取 3 → 插入到 2 和 4 之间 → 最终有序数组 [1,2,3,4,5,6]
示例代码：
def insertion_sort(arr):
# 从第 2 个元素开始遍历（索引 1）
for i in range(1, len(arr)):
# 当前要插入的元素
current = arr[i]
# 已排序部分的最后一个元素索引
j = i - 1
# 向前遍历已排序部分，找到插入位置
# 如果当前元素比前面的元素小，就把前面的元素往后挪
while j >= 0 and current < arr[j]:
arr[j + 1] = arr[j] # 元素后移
j -= 1
# 退出循环时，j+1 就是正确的插入位置
arr[j + 1] = current
return arr
if __name__ == "__main__":
test_list = [5, 2, 4, 6, 1, 3]
print("原始数组:", test_list)
sorted_list = insertion_sort(test_list)
print("排序后:", sorted_list)运行结果：
原始数组: [5, 2, 4, 6, 1, 3]
排序后: [1, 2, 3, 4, 5, 6]
川公网安备51010802032098