1.插入排序的含义
- 类似扑克牌，假设认为0-0位置有序，再把0-1的位置变有序，循环直到所有的有序。每次拿取右侧的数字，一个一个对比放到左侧来。
2.示例代码
def insertion_sort(arr):if arr is None or len(arr) < 2:returnfor i in range(1, len(arr)):# 0 ~ i-1 有序,新来的是[i]向左看# 遍历一遍,把右侧新的无序[i],向左侧一个一个比较,放到合适的位置上key = i - 1 # 当前数的前一个位置# j+1是当前数# 1 4 5 | 2 # 现在2是无序的while key >= 0 and arr[key] > arr[key + 1]: # 5比2大吗?arr[key], arr[key + 1] = arr[key + 1], arr[key] # 交换后1 4 2 5key -= 1 # 新的key是2的位置# Example usage
arr = [3, 2, 1, 5, 4]
insertion_sort(arr)
print(arr) # Output: [1, 2, 3, 4, 5]3.练习代码
def insertion_sort(arr):n = len(arr)for i in range(1,n):key = i-1while key >=0 and arr[key] > arr[key+1]: # 向左侧冒泡arr[key],arr[key+1] = arr[key+1],arr[key]key -= 1return arrarr = [1,2,5,8,3]
print(insertion_sort(arr))4.截图
5.感悟
- 加油，总以为自己不行，实际上自己很厉害！
6.代码思路
- 感觉设置一个key更好理解。
7.参考文献
动图：https://www.runoob.com/w3cnote/insertion-sort.html
代码：https://github.com/algorithmzuo/algorithm-journey/blob/main/src/class004/SelectBubbleInsert.java
视频：https://www.bilibili.com/video/BV12P41147to/?spm_id_from=333.999.0.0&vd_source=6176e79b66461eb74da787cb8321925b
