3.排序算法（3）

1.插入排序介绍

1. 需准备一个临时变量，每轮比较将待比较数放入
2. 临时变量和待比较数的前一个数据比较，大数靠后右移动，找到临时变量中值的插入位置
3.每一轮结束后，得到一个从开始到待比较位置的一个有序序列

动态效果：https://www.runoob.com/w3cnote/insertion-sort.html

2.代码实现

lst = [2, 5, 23, 6, 0, 78, 68]
def insert_sort(lst:list):
    for i in range(1,len(lst)):
        j = i - 1
        temp = lst[i]
        while j >= 0 and lst[j] > temp:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = temp

print(lst)
insert_sort(lst)
print(lst)

# 运行结果
[2, 5, 23, 6, 0, 78, 68]
[0, 2, 5, 6, 23, 68, 78]

3.总结

1.最好的情况，正好是升序排列，迭代n-1次，最差情况正好是降序排列，比较迭代n(n-1)/2
2.使用两层嵌套循环，时间复杂度O(n^2)
3.是稳定的排序算法，适用于小规模数据比较
4.如果操作耗时较大，可适当优化，使用二分查找插入排序