插入排序是一种简单直观的排序算法，其工作原理类似于我们平时整理扑克牌或书籍的方式。它的核心思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的适当位置，从而保持已排序部分的有序性。
插入排序的原理
1）初始状态：假设数组的第一个元素是已排序的，其余元素是未排序的。
2）遍历：从数组的第二个元素开始，依次取出每一个元素。
3）插入：对于每一个取出的元素，将其与已排序部分的元素进行比较，找到其应该插入的位置，并将其插入。
4）重复：重复上述步骤，直到所有元素都被插入到已排序部分，此时整个数组即为有序。
Python代码实现
def insertion_sort(arr):
# 遍历从第二个元素到最后一个元素
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] # 将arr[j]向右移动一位
j -= 1
arr[j + 1] = key # 插入key
return arr
# 测试代码
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6]
print("排序前的数组:", arr)
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)