排序思想
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
类比摸牌
- 初始时手里（无序区）只有一张牌
- 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
- 如果是大的数，把数直接放在左侧，如果是小的数，把比它大的数移动一位，再插入
图解分析插入排序
测试的列表：[3, 2, 4, 1, 5, 7, 9, 6, 8]
（1）原始数据
原始排序
（2）排序过程
A代表的是列表，j代表的是已经排好序的牌。temp代表的是抽到的牌，即将放到牌堆当中。
第1轮：
第1轮, i = 1
原始数据是：3,2,4,1,5,6,9,6,8
可以分为有序区 [3] 和 无序区 [2,4,1,5,6,9,6,8]
抽取的牌是 temp = A[i] = A[1] = 2
手中的牌的下标是 j = i - 1 = 0，牌是 A[j] = 3
A[j] = 3 大于 temp = 2，说明此时的牌需要进行交换
且 j = 0，说明还有位置可以交换
所以 A[j + 1] = A[j] = 3，相当于把比较的牌后移一位
此时列表为: 3,3,4,1,5,6,9,6,8
进行左移，j = j - 1 = 0 - 1 = -1 < 0，循环结束，并且 A[j + 1] = A[-1 + 1] = A[0] = temp = 2
相当于把抽到的这张小牌放在最开始的位置
此时列表: 2,3,4,1,5,6,9,6,8
第1轮
第2轮
第2轮, i = 2
此时列表分为
有序区：2,3
无序区: 4,1,5,6,9,6,8
抽取的牌是 temp = A[i] = A[2] = 4
手中的牌的下标是 j = i - 1 = 1，牌是 A[j] = 3
A[j] = 3 小于 temp = 4，不进行交换。
因为有序区的最大的数依然小于无序区的第一个数，因此不进行交换，结束循环
此时的列表是 2,3,4,1,5,6,9,6,8
相当于抽到一个比之前所以的牌都大的牌，直接放在最后面就行
第2轮
第3轮
第3轮，i = 3
此时列表分为
有序区：2,3,4
无序区: 1,5,6,9,6,8
抽取的牌是 temp = A[i] = A[3] = 1
手中的牌的下标是 j = i - 1 = 3 - 1 = 2，牌是 A[j] = 4
A[j] > temp，因此 A[j+1] = A[j] = 4，并且左移一位，j = 1
此时列表变为 2, 3, 4, 4, 5, 7, 9, 6, 8
此时比较的牌是 A[j] = A[1] = 3 < temp，因此 A[j+1]=A[j]=3，并且左移一位，j=0
此时列表变为：2,3,4,5,6,7,9,6,8
此时比较的牌是 A[j] = A[0] = 2 < temp，因此 A[j+1]=A[j]=2，并且左移一位，j=-1，结束循环
A[j+1]=A[0]=temp=2，第一位就放的是自己抽取的牌
相当于抽到一个比较小的牌，但是与之前已经拿好的牌一一进行比较，把前面的牌往后放，小的牌插进去
截屏2024-01-11 21.27.32.png
代码
def insert_sort(target_list):
# 先拿到一个数，然后继续摸牌
for i in range(1, len(target_list)): # i 表示摸到的牌的下标
temp = target_list[i] # 存摸到的牌
j = i - 1 # j 指的是手里的牌的下标
# 下一张牌比之前的牌大，并且 j >= 0
# 有序区的牌会不断地移动，给新的牌让位置。
# 这个循环就是找插入的位置
while j >= 0 and target_list[j] > temp:
target_list[j + 1] = target_list[j]
j -= 1 # j的箭头往左移动
target_list[j+1] = temp
test_list = [3, 2, 4, 1, 5, 7, 9, 6, 8]
print("排序之前: ", test_list)
insert_sort(test_list)
print("排序之后: ", test_list)
结果
排序之前: [3, 2, 4, 1, 5, 7, 9, 6, 8]
排序之后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
时间复杂度
因为这个算法是 for 和 while 结合的算法，但是while循环是和 j 相关的，j是和 n相关的，因此时间复杂度是
算法时间的估算
的排序运行时间，一般来说电脑1秒钟运行的次数是
，比如 n = 10000，那么运行时间就是
秒左右
网友评论