03 插入排序

1.插入排序的含义

• 类似扑克牌，假设认为0-0位置有序，再把0-1的位置变有序，循环直到所有的有序。每次拿取右侧的数字，一个一个对比放到左侧来。

2.示例代码

def insertion_sort(arr):
    if arr is None or len(arr) < 2:
        return
    for 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 5
            key -= 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-1
        while key >=0 and arr[key] > arr[key+1]:    # 向左侧冒泡
            arr[key],arr[key+1] = arr[key+1],arr[key]
            key -= 1
    return arr

arr = [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