资源简介

(共22张PPT)
课时32 插入排序
一、插入排序算法的基本思想
插入排序的思想是将待排序的元素一个个地插入已排好序的部分中，逐步构建有序序列。插入排序算法的基本思路是将数组分成已排序部分和未排序部分，然后每次从未排序部分取出一个元素，插入已排序部分的适当位置，使得已排序部分仍然保持有序。
如图所示，在有序序列中插入数据 9，需要先将有序序列中大于 9 的元素从后往前依次向后移 1 位，然后将数据 9 插入到有序序列中。
二、插入排序算法的过程
1. 在最好情况下，即待排序序列已经是有序的情况下，每次插入一个元素只需要比较一次就可以确定其位置，时间复杂度为 O(n)。
2. 在最坏情况下，即待排序序列是逆序的情况下，每次插入一个元素需要比较 1，2，…，n-1 次才能找到其位置，总共需要比较 n(n-1)/2次，时间复杂度为 O(n2)。
三、插入排序算法的算法效率
def insertion_sort(a):
#从第二个元素开始，与前面的元素进行比较
for i in range(1,len(a)):
tmp=a[i] #当前元素（待插入元素）
pos=i-1 #前一个元素的索引
#在有序部分寻找插入位置
while pos>=0 and a[pos]>tmp:
#逐位后移
a[pos+1]=a[pos]
pos-=1
a[pos+1]=tmp #将当前元素插入有序部分
return a
四、插入排序的 Python 实现
典例 1 对数组元素 a[0]到 a[4]进行插入排序，经过第 1 遍排序加工后，数组元素 a[0]到 a[4]的数据依次是“15,54,8,45,21”，则下一遍排序加工后，数组元素 a[0]到 a[4]的数据依次是 （　　）
A.8,54,15,45,21
B.8,15,54,45,21
C.8,15,54,21,45
D.15,8,45,21,54
B
√
题型导向一　插入排序的原理
胜券点拨1
明考向 本题主要考查插入排序的原理和过程
审关键 每次将一个待排序的数据插入到前面的有序序列中，使有序序列仍然有序
考场思 维快闪 第1遍插入排序加工后，前2个元素为有序序列，则第2遍插入排序加工时，待插入元素为8，插入到有序序列中为8,15,54，其余元素的位置保持不变
典例 2 ［2025 七彩阳光联盟］有如下 Python程序段：
a=[11,4,2,13,6,5,3,6,19,1]
for i in range(1,len(a)):
key=a[i]
j=i
while 　　　（1）　　　:
a[j]=a[j-1]
j-=1
　　　（2）　　　1
画线处有如下可选代码：
①j>0 and key=0 and key③a[j]=key ④a[j-1]=key
为使数组 a 实现升序排序，画线处应填入的正确代码为 （　　）
A.①③ B.①④ C.②③ D.②④
A
√
题型导向二　插入排序的 Python 实现
胜券点拨2
明考向 本题考查插入排序算法的程序实现
审关键 插入排序算法实现过程中语句的作用
考场思 维快闪 该程序段将a[i]插入至已经有序的a[0]~a[i-1]中，故需要将a[i]和a[0]~a[i-1]进行比较。（1）将a[i]的值存入key中，a[0]~a[i-1]的元素采用j-1来进行枚举，所以j的取值最小只能为1，当j的值为0时，不再继续执行，故填入代码为j>0 and key典例 3 有如下 Python 程序段：
d=[5,9,10,7,8,20,6,0]
for i in range(1,len(d)):
k=d[i]
j=i-1
while d[j]>k:
d[j+1]=d[j]
j-=1
if j==-1:
break
d[j+1]=k
print(d)
执行该程序段后，输出的结果是 （　　）
A.[20,10,9,8,7,6,5,0] B.[0,5,6,7,8,9,10,20]
C.[5,9,10,7,8,20,6,0] D.[5,6,7,8,9,10,20,0]
B
√
胜券点拨3
明考向 本题考查插入排序算法的程序实现
审关键 插入排序算法实现过程中的语句作用
考场思 维快闪 该程序段实现对数组d进行升序的插入排序，for循环从第2个元素开始，与前面的元素进行比较，若前一个元素大于当前元素，则把前一个元素后移一位，然后继续往前比较，若比较完第一个位置，则用break语句退出while循环，然后将当前元素插入到正确的位置
典例 4 有如下 Python 程序段：
a=[19,8,96,92,85,88]
for i in range(1,4):
temp=a[i]
j=i-1
while temp=0:
a[j+1]=a[j]
j=j-1
a[j+1]=temp
print(a)
执行该程序段后，输出的结果是 （　　）
A.[8,19,92,96,85,88]
B.[8,19,85,88,92,96]
C.[19,8,92,96,85,88]
D.[19,8,85,92,96,88]
A
√
题型导向三　插入排序的变式
胜券点拨4
明考向 本题主要考查插入排序算法的变式
审关键 外循环决定排序的轮数
考场思 维快闪 根据for循环的范围可知，该程序段先后将a[1]、a[2]、a[3]作为待插入数据进行排序，因此执行该程序段后，前4个元素升序排序，后面2个元素保持不变
典例 5 ［2025.1 浙江选考］数组元素 a[0]~a[n-1]已按升序排列，现要将 a[pos]（0≤pos≤n-1）的值加 1，并保持数组的有序性不变，实现该功能的程序段如下，方框中应填入的正确代码为 （　　）
t=a[pos]+1
i=pos
while 　　　　　　　 :
a[i]=a[i+1]
i+=1
a[i]=t
A.ia[i+1]
C.ia[i+1] D.i<=n-1 or t>a[i]
B
√
胜券点拨5
明考向 本题考查插入排序算法
审关键 保持数组的有序性不变
考场思 维快闪 初始变量t为a[pos]的值加1（并没有改变a[pos]的值），变量i从pos位置开始遍历数组元素，若t大于它后面的数a[i+1]，则将a[i+1]的值向前移动一位，直到a[i+1]大于或等于t，最后将a[i]赋值为t。由于比较的对象是t和a[i+1]，因此i的值不能超过n-2，即i典例 6 有如下 Python 程序段：
d=[9,3,1,8,4,2]
s=[0,1,2,3,4,5]
n=len(d)
for i in range(1,n):
key=s[i]
j=i-1
while j>=0 and d[s[j]]>d[key]:
s[j+1]=s[j]
j-=1
s[j+1]=key
print(s)
执行该程序段后，第 4 行输出的内容是 （　　）
A.[2,5,1,4,3,0] B.[2,1,3,0,4,5] C.[2,1,4,3,0,5] D.[2,1,0,3,4,5]
C
√
胜券点拨6
明考向 本题考查插入排序算法的变式
审关键 对索引进行排序
考场思 维快闪 该程序段每轮循环将未排序部分的元素插入到已排序部分的适当位置，则第4轮循环后，列表d中的前5个数实现升序排列，结果为[1,3,4,8,9]，但排序过程中不改变数据列表d，只改变索引列表s，故得到s[:5]为[2,1,4,3,0]，此时第6个数还未参加排序，s[5]仍为5，故第4行输出的内容是[2,1,4,3,0,5]
while j>pos and a[j-1]>tmp:
a[j]=a[j-1]
　　　③　　　1
a[j]=tmp
print(a)
典例 7 使用插入排序算法对列表 a 进行排序，要求奇数和偶数各自按升序排序，其中奇数在前，偶数在后。例如，数组 a=[4,5,2,9,6,7,10,3,8,1]的排序结果为[1,3,5,7,9,2,4,6,8,10]。实现上述功能的 Python 程序如下，请在画线处填入合适的代码。
n=10
a=[4,5,2,9,6,7,10,3,8,1]
pos=0 #pos 指向第一个已排序偶数的下标
for i in range(n):
tmp=a[i]
j=i
if tmp%2==1:
while 　　　①　　　 or a[j-1]>tmp and j>0:
a[j]=a[j-1]
j=j-1
pos= 　　　②　　　1
else:
j>pos
pos+1
j=j-1
胜券点拨7
明考向 本题主要考查插入排序算法
审关键 奇数在前，偶数在后
考场思维快闪 ① 若tmp为奇数，则将偶数以及大于tmp的元素都向后移一位，故填入代码为j>pos
② 因为奇数会插入到偶数的前面，所以第一个已排序偶数的下标需要后移一位，故填入代码为pos+1
③ 若tmp为偶数，则将大于tmp的偶数都后移一位，为了继续向左比较，每次j的值都要减1，故填入代码为j=j-1
1.在上体育课的时候同学们随便排了队伍，老师要求按照身高从低到高依次排队，如果按照插入排序算法，第一步要做的是 （　　）
A.前2位同学从高到低排
B.前2位同学从低到高排
C.最高的同学跟最低的同学交换位置
D.最高的同学跟第一位同学交换位置
插入排序算法的基本思路是将数组分成已排序部分和未排序部分，然后每次从未排序部分取出一个元素，插入已排序部分的适当位置，使得已排序部分仍然保持有序。故第一步要做的是前2位同学从低到高排，其余学生在已排序好的学生序列中找到合适的位置依次插入即可。
一、插入排序的原理
B
√
2.有如下Python程序段：
a=[6,1,4,8,2,4,7,9]
for i in range(1,len(a)):
t,j=a[i],i-1
while j>=0 and a[j]>t:
a[j+1]=a[j]
j-=1
a[j+1]=t
执行该程序段后，a[3]的值为 （　　）
A.4 B.6 C.7 D.8
外层循环变量i指向当前待排序元素，也可以看作待排序区域的左边界，每趟排序的结果就是把a[i]插入到合适位置实现升序排序；内层循环变量j从已排序区域的右端向左扫描，比较和移动元素，直到找到插入位置。故完成排序后，a的值是[1,2,4,4,6,7,8,9]。
A
√
二、插入排序的Python实现
3.有如下Python程序段：
a=[1,8,4,6,2,3,7,9]
for i in range(1,len(a)):
j=i
while j>0 and a[j]a[j],a[j-1]=a[j-1],a[j]
j-=1
执行该程序段后，a[2]的值为 （　　）
A.3 B.4 C.7 D.8
A
√
本题考查插入排序算法。外层循环变量i指向当前待排序元素，每趟排序的结果就是把a[i]向左交换到合适位置；内层循环变量j从已排序区域的右端向左扫描，比较和交换元素，直到找到合适位置，最终得到a的值为[1,2,3,4,6,7,8,9]。
4.有如下Python程序段：
from random import randint
a=[randint(1,10) for i in range(5)]
for i in range(1,5):
key=randint(3,6)*2
j=i-1
while j>=0 and keya[j+1]=a[j]
j-=1
a[j+1]=key
执行该程序段后，列表a的值不可能是 （　　）
A.[3,6,8,10,12] B.[1,5,8,9,12]
C.[6,10,10,12,12] D.[8,9,10,10,12]
B
√
数组a中的初始值为5个1～10之间的随机整数，变量key的取值为6、8、10、12。for循环执行4次，表示插入4次key，while循环的作用是将key插入数组a中并保持元素非降序排列，若key小于a[j]，则往前找到key不小于a[j]的位置插入；若key大于等于a[j],则在a[j]之后插入key。故执行程序段后，数组a中后4个元素的值一定大于等于6，且为非降序排列。
三、插入排序的变式
5.［2025绍兴模拟］有如下Python程序段：
p=0
for i in range(len(a)):
if not ("a"<=a[i]<="z"):
j=i
pt=a[i]
while j>p:
a[j]=a[j-1]
j=j-1
p=j
a[j]=pt
print(a[4])
若列表a=["-","p","y","-","t","h","o","n","-"]，则执行该程序段后，输出的结果是 （　　）
A.- B.p C.y D.t
该程序段将非英文字符插入到英文字符的前面，最终得到a的值为["-","-","-","p","y","t","h","o","n"]。故a[4]的值为"y"。
C
√
6.有如下Python程序段：
#随机产生5个整数，存储在列表a中
for i in range(1,5):
k=a[i]
j=i-1
while j>=0 and abs(a[j]-2)>abs(k-2):
a[j+1]=a[j]
j-=1
a[j+1]=k
执行该程序段后，列表a的值可能是 （　　）
A.[-5,-2,4,0,1] B.[3,-1,0,2,-3]
C.[0,4,0,-2,-4] D.[1,2,3,4,5]
该程序段采用插入排序算法，根据元素减2的绝对值对列表a进行升序排序，元素本身的值不变。选项A，元素减2取绝对值得到[7,4,2,2,1]，没有升序排序。选项B，元素减2取绝对值得到[1,3,2,0,5]，没有升序排序。选项C，元素减2取绝对值得到[2,2,2,4,6]，升序排序。选项D，元素减2取绝对值得到[1,0,1,2,3]，没有升序排序。
C
√
7.操作系统管理n个连续的内存单元，地址编号为0～n-1，可动态分配给多项作业使用。现有一个作业队列，其中记录了各项作业申请的内存单元数量、作业请求等情况。某作业执行时，会向系统请求分配一段连续的空闲块（简称“块”），执行完后由系统回收该空闲块（回收后若存在连续的多个空闲块，则合并为一块）。
　　系统分配内存的方法是：按作业请求从所有空闲单元中尽可能地挑选一个能满足要求的最小空闲块，当有多块满足要求时，选择起始地址编号最小的空闲块（能分配时则从该空闲块的起始地址开始分配；不能分配时则提示内存不足）。编写Python程序模拟动态分配过程。请回答下列问题：
（1）设有500个内存单元，地址编号为0～499，初始全部空闲。某队列作业顺序执行情况如图所示，则作业“J6”申请到的内存块起始地址编号为　　　　　　　。
作业编号 内存块大小 作业请求
J1 160 分配
J2 64 分配
J3 120 分配
J4 86 分配
J1 160 回收
J3 120 回收
J5 70 分配
J6 64 分配
224
top=-1
j=m-1
while j>=0:
tmp=lst[j]
while top!=-1 and free[tmp][1]>
　　　①　　　:
lst[j]=stk[top]
j+=1
top-=1
top+=1
　　　②　　　1
j-=1
while top>-1:
j+=1
lst[j]=stk[top]
top-=1
return lst
（2）定义如下函数sortbysize(free)，参数free为链表的各节点由空闲块的起始地址、块大小、链接地址描述，并按起始地址升序。函数功能是保持free的链接结构不变，返回列表lst，lst是free中各节点按块大小升序、块大小相同按起始地址升序的索引序列。请在画线处填入合适的代码。
def sortbysize(free):
'''对链表free进行排序，free[0]为头节点，描述了链表的头指针、空闲块个数'''
lst=[]
#free[0][0]为链表的头指针
p=free[0][0]　
while p!=-1:
lst.append(p)
p=free[p][2]
m=free[0][1]
stk=[-1]*m
free[stk[top]][1]
stk[top]=tmp
（3）执行语句lst=sortbysize([[1,4],[0,160,2],[200,120,3],[350,70,4],
[442,70,-1]])，在执行过程中，变量top的值最大为　　 　　，执行后lst的值为　　　　　　　。
3
[3,4,2,1]
（1）J1~J4分配的地址块分别是：J1：0~159；J2：160~223；J3：224~343；J4：344~429。此时空闲块为430~499（大小70），回收J1和J3之后，空闲块为0~159（大小160）、224~343（大小120）、430~499（大小70）。故为J5分配空闲块430~499，为J6分配剩余较小空闲块224~343，故起始地址编号为224。　（2）①处自定义函数中，free与普通链表不同，是一个带头节点的链表，头节点free[0]中存储两个数据，分别是链表的头指针和内存块数量。所以，m表示空闲块数量，借助一个栈stk存储free中的节点下标，从后往前遍历链表free中的节点。要求将free中的数据按照块大小升序、块大小相同时按照起始地址升序的规则存入列表lst，那么元素在栈中应是按主次关键字降序排序（正好相反）。因此在当前节点的块大小大于栈顶元素的块大小时，将栈中较小元素出栈（出栈过程中，依次将出栈的元素存入lst中，使元素在lst中保持升序），再将当前节点的位置入栈。此处获取栈顶元素的块大小，故填入代码为free[stk[top]][1]。②处将当前节点的位置入栈，故填入代码为stk[top]=tmp。　（3）执行之后，节点下标按照块大小在stk中降序排列，故top值最大为3。节点下标按块大小升序、内存地址升序的主次关键字顺序在lst中排列，故lst终值为[3,4,2,1]。

展开更多......

收起↑