资源简介

(共47张PPT)
课时30 冒泡排序
一、排序
1. 排序的概念：排序就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，但其在序列中的顺序可能会改变。
2.待排序数据的存储方式。
（1）数组：将数据依次存放在一组地址　　　　的存储单元中，在这种情况下，排序过程是对数据本身进行物理重排，即通过关键字之间的比较判断，将数据移到合适的位置。
（2）链表：排序过程中无须移动数据，仅需修改指针即可。
连续
1.sort()：sort()方法只适用于　　　　，直接对列表进行排序，不会产生新的序列。
2.sorted()：内建函数 sorted()方法返回一个新的排序后的序列，而原来的序列依旧存在。
列表
二、Python 中的排序函数
3.两者的使用方法如下：
>>>a=[5,7,6,3,4,1,2]
>>>b=sorted(a) #默认升序排序
>>>c=sorted(a,reverse=True) #降序排序
>>>print(a)
[5, 7, 6, 3, 4, 1, 2]
>>>print(b)
[1, 2, 3, 4, 5, 6, 7]
>>>print(c)
[7, 6, 5, 4, 3, 2, 1]
>>>a.sort() #默认升序排序
>>>print(a)
[1, 2, 3, 4, 5, 6, 7]
>>>a.sort(reverse=True) #降序排序
>>>print(a)
[7, 6, 5, 4, 3, 2, 1]
1. 冒泡排序是在一系列数据中对　　　　两个数依
次进行比较和调整，让较大的数“下沉（上冒）”，
较小的数“上冒（下沉）”的一种排序技术。
2.冒泡排序的过程。
（1）上冒：通过从下往上的两两比较，将值最小的
元素“上冒”到数组下标为 0 的位置，如图 a 所
示。若要完成数组 a 中全部元素的升序排序，则需
要再进行最多 4 轮的“冒泡”。
（2）下沉：通过从上往下的两两比较，将值最大的
元素“下沉”到数组下标为 5 的位置，如图 b 所
示。若要完成数组 a 中全部元素的升序排序，则需
要再进行最多 4 轮的“冒泡”。
相邻
三、冒泡排序
3. 冒泡排序的算法效率。对于有 n 个元素的数组，共需要 n-1 遍加工。第 1 遍加工的比较次数为 n-1 次，第 2 遍加工的比较次数为 n-2 次，以此类推，最后一遍加工的比较次数为 1 次。所以用冒泡排序算法进行排序时，总共的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2 次，其时间复杂度为 O(n2)。
4. 冒泡排序的 Python 实现，以从前往后进行比较实现升序为例。
def bubble_sort(d):
length=len(d)
#序列长度为 length，需要执行 length-1 遍加工
for i in range(1,length):
for j in range(0,length-i):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
典例 1 ［2025 浙江 A9 协作体］若采用冒泡排序算法对数据序列 22，35，43，56，19，8 进行升序排序，则共需要交换的次数为 （　　）
A.9 次
B.12 次
C.15 次
D.21 次
A
√
题型导向一　冒泡排序的原理
胜券点拨1
明考向 本题主要考查冒泡排序的原理和过程
审关键 冒泡排序中数据交换的次数
考场思 维快闪 冒泡排序的交换次数等于逆序对的个数，22与19、8构成2个逆序对，35与19、8构成2个逆序对，43与19、8构成2个逆序对，56与19、8构成2个逆序对，19与8构成1个逆序对，共9对，故共需要交换9次
典例 2 采用冒泡排序算法对某数据序列进行排序，经过第一轮排序后的结果是“2,8,3,9,5,6,7”，则原数据序列不可能是 （　　）
A.8,3,9,5,2,7,6
B.8,3,9,2,6,5,7
C.8,2,9,3,5,7,6
D.8,3,2,9,6,5,7
D
√
胜券点拨2
明考向 本题主要考查冒泡排序的基本思想
审关键 每一轮冒泡结束后必有一个数被调整到正确位置
考场思 维快闪 由第一轮排序结果可知，最小值2处于最前面的正确位置，则该冒泡排序实现的是从后往前的升序排序。选项D的第一轮排序结果为“2,8,3,5,9,6,7”
典例 3 某升序冒泡排序算法的 Python 程序段如下：
#随机生成 n 个整数，依次存入数组 a 中，代码略
for i in range(1,n):
for j in range(　　　　　　　):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
画线处应填入的代码是 （　　）
A.n-i-1 B.n-i
C.n-i+1 D.n
B
√
题型导向二　冒泡排序的Python实现
胜券点拨3
明考向 本题考查冒泡排序算法的程序实现
审关键 冒泡排序算法实现过程中的语句作用
考场思 维快闪 在升序冒泡排序中，外层循环控制排序的轮数，内层循环控制每一轮的比较次数。第一轮比较n-1次，第二轮比较n-2次，以此类推，第i轮比较n-i次。故内层循环的范围是range(n-i)
典例 4 有如下 Python 程序段：
s=[2,3,4,9,7,8,5]
n=len(s)
for i in range(n-1):
for j in range(n-1,i,-1):
if s[j]s[j],s[j-1]=s[j-1],s[j]
下列说法正确的是 （　　）
A.整个加工过程总的交换次数为 21
B.执行该程序段后，s 的值为[9,8,7,5,4,3,2]
C.每一遍加工过程中，最小的元素“上冒”
D.若 s 的初始值已经有序，则该算法的时间复杂度为 O(1)
C
√
胜券点拨4
明考向 本题考查冒泡排序算法的程序实现
审关键 冒泡排序算法实现过程中的语句作用
考场思维快闪 该排序算法当s[j]典例5　［2026宁波模拟］有如下Python程序段：
#"a"的ASCII码值是97
arr=["a","d","d","r","e","s","s"]
n=len(arr)
for i in range(n-1,0,-1):
for j in range(n-2,n-i-2,-1):
if ord(arr[j])%3>ord(arr[j+1])%3:
arr[j],arr[j+1]=arr[j+1],arr[j]
print(arr)
运行该程序段后，arr的值是 （　　）
A.["e","a","d","d","s","s","r"]
B.["e","s","s","d","d","a","r"]
C.["r","a","d","d","s","s","e"]
D.["r","s","s","d","d","a","e"]
C
√
题型导向三　冒泡排序的变式
胜券点拨5
明考向 本题主要考查冒泡排序算法的变式
审关键 冒泡排序算法实现过程中的语句作用
考场思维快闪 该程序段基于字符ASCII码值除以3的余数对列表arr进行排序，使余数非降序排序。"a"、"d"、"r"、"e"、"s"的ASCII码值除以3的余数分别为1、1、0、2、1，余数相同时不会进行交换
典例 6 ［2023.1 浙江选考］列表 s 包含 8 个互不相等的元素，即 s[0]，s[1]，s[2]，…，s[7]，有如下 Python 程序段：
n=8
for i in range(1,n-1):
for j in range(1,n-i-1):
if s[j]>s[j-1]:
s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是 （　　）
A.s[0]到 s[5]的降序排序 B.s[1]到 s[6]的降序排序
C.s[1]到 s[7]的升序排序 D.s[2]到 s[6]的升序排序
A
√
胜券点拨6
明考向 本题考查冒泡排序算法的变式
审关键 冒泡排序算法实现过程中的语句作用
考场思维快闪 外循环变量i的取值范围是1～6，当i为1时，内循环变量j的取值范围是1～5，由于参与比较的两个元素下标分别是j和j-1，故将列表元素s[0]～s[5]从前向后进行比较排序，由s[j]>s[j-1]可知，当后一个数大于前一个数时要发生交换，故最终排序结果是降序
典例 7 ［2025 强基联盟］有如下 Python 程序段：
#随机生成 5 个正整数并存入列表 s 中，代码略
def sort_indices(s):
n=len(s)
y=[i for i in range(n)] #生成序列 0~n-1
for i in range(n-1):
for j in range(n-i-1):
if s[y[j]]>=s[y[j+1]]:
y[j],y[j+1]=y[j+1],y[j]
return y
若函数返回的结果为[2,1,0,4,3]，则列表 s 的值可能是 （　　）
A.[3,2,1,5,4] B.[4,2,1,5,3] C.[5,2,1,3,4] D.[3,2,5,1,4]
A
√
胜券点拨7
明考向 本题考查冒泡排序算法的变式
审关键 对索引进行排序
考场思 维快闪 sort_indices(s)函数的功能是根据列表s中的元素大小，对元素进行升序排序，但移动的是序列y中的元素。已知返回的结果为[2,1,0,4,3]，对应列表s中的元素大小位置，故列表s的值可能是[3,2,1,5,4]
典例8　［2026金华十校联考］有如下Python程序段：
a=[2,-1,-4,0,0,-2]
L=-1;R=6;i=0
while iif a[i]<0:
L=L+1
a[i],a[L]=a[L],a[i]
i=i+1
elif a[i]>0:
R=R-1
a[i],a[R]=a[R],a[i]
else:
i=i+1
运行该程序段后，列表a的值为 （　　）
A.[-4,-1,-2,0,0,2] B.[-2,-1,-4,0,0,2]
C.[0,0,-2,-1,-4,2] D.[-1,-2,-4,0,0,2]
B
√
胜券点拨8
明考向 本题主要考查分区、排序思想
审关键 将数组元素按负数、零和正数进行分组
考场思维快闪 该程序遍历列表a，若当前元素a[i]为负数，则L右移一位，然后交换a[i]与a[L]，然后i右移一位；若当前元素a[i]为正数，R左移一位，然后交换a[i]与a[R]，i不变；若当前元素a[i]为0，则i右移一位。最终实现列表a中负数在左边，零在中间，正数在右边。当i=0时，a[0]=2>0，R左移一位为5，然后a[0]与a[5]交换，a变为[-2,-1,-4,0,0,2]，之后不再改变元素位置
典例 9 有如下 Python 程序段：
n=8
cnt1=cnt2=0
flag=True
last=0
d=[1,2,4,6,7,9,5,8]
while last<=n-2 and flag:
flag=False
for j in range(n-1,last,-1):
cnt1+=1
if d[j]d[j-1],d[j]=d[j],d[j-1]
cnt2+=1
flag=True
pos=j
last=pos
执行该程序段后，变量 cnt1 和 cnt2 的值分别是（　　）
A.28 和 4 B.10 和 4 C.28 和 24 D.13 和 24
B
√
题型导向四　冒泡排序的优化
胜券点拨9
明考向 本题考查冒泡排序算法的优化
审关键 通过flag变量标记是否交换元素、通过last变量缩小比较区间
考场思 维快闪 while循环用于控制排序的轮次，每轮循环都将flag设置为False。for循环表示从后往前冒泡，每轮将较小值冒泡到最前面。for循环每执行一次，cnt1的值加1。每交换一次，cnt2的值加1，同时将flag设置为True，pos记录最后一个交换的元素位置。当for循环结束时，last中保存了当前轮中最后一次交换时j的位置，当last大于n-2或flag为False时，while循环结束。当d=[1,2,4,6,7,9,5,8]时，第一轮排序后，得到d=[1,2,4,5,6,7,9,8]，cnt1的值为7，cnt2的值为3，last的值为4，flag的值为True。第二轮排序后，得到d=[1,2,4,5,6,7,8,9]，cnt1的值为7+3=10，cnt2的值为3+1=4，last的值为7，flag的值为True，此时last大于n-2，while循环结束
典例 10 ［2025 金丽衢联考］如下 Python 程序段实现对数组 a 中的元素 a[0]~a[5]进行升序排序：
a=[27,34,53,54,55,42]
n=len(a);start=0
while start!=n-1: #语句①
last=n-1
for j in range(n-1,start,-1):
if a[j]a[j],a[j-1]=a[j-1],a[j] #语句③
last=j
start=last
print(a)
执行该程序段后，下列说法不正确的是 （　　）
A.加框处代码第一次执行结束后，start的值为 3
B.语句①可以修改为“while startC.语句②共执行了 6 次
D.语句③共执行了 3 次
C
√
胜券点拨10
明考向 本题考查冒泡排序算法的优化
审关键 通过start变量缩小比较区间
考场思维快闪 A 加框处代码第一次执行结束后，完成第一轮排序，第一轮最后交换的元素是a[2]和a[3]，故此时start的值为3
B start从0开始逐步后移，直到start为n-1时完成排序，因此条件“while start!=n-1:”与“while startC 语句②表示排序过程中相邻元素的比较次数，第一轮排序比较5次，第二轮排序比较2次，共7次
D 语句③表示排序过程中相邻元素的交换次数，即数组a中的逆序对数，故共执行了3次
遍历顺序 排序规则 实现过程
正序 （从左到右） 升序 从左到右，进行相邻元素的两两比较，将较大的元素交换到右边。逐个将剩余未排序元素中的最大值排列在序列最右边，最终完成升序排序
降序 从左到右，进行相邻元素的两两比较，将较小的元素交换到右边。逐个将剩余未排序元素中的最小值排列在序列最右边，最终完成降序排序
逆序 （从右到左） 升序 从右到左，进行相邻元素的两两比较，将较小的元素交换到左边。逐个将剩余未排序元素中的最小值排列在序列最左边，最终完成升序排序
降序 从右到左，进行相邻元素的两两比较，将较大的元素交换到左边。逐个将剩余未排序元素中的最大值排列在序列最左边，最终完成降序排序
注意：实现过程中加点的部分，即不同实现过程的区别，比较的方法一致，为两两比较，根据排序规则进行交换
通法一　冒泡排序的实现原理
1. 利用 Python 实现的冒泡排序的经典代码如下，其他扩展功能可在该代码的基础上进行变通及修改：
def bouble_sort(li):
n=len(li)
for i in range(　　　①　　　):
for j in range(　　　②　　　):
if 　　　③　　　:
　　　④　　　1
2.①处代码控制冒泡加工的轮次；②处代码确定排序的下标范围和比较方向，下标 j 的范围与代码③联动，不可超出数组下标；③处代码决定升序或降序排序，若比较 j和 j+1 的元素，则 j的范围是[0,n-2]，若比较 j-1 和 j的元素，则 j 的范围是[1,n-1]，前者>后者则为升序，前者<后者则为降序；④处代码交换元素，代码③比较哪两个元素则交换哪两个元素。
通法二　Python实现冒泡排序的重要语句
3. 如表所示是常见冒泡排序算法中，①～③代码的组合方式，注意当其中一句代码发生变化时，其他代码将联动变化。
对应代码 实现效果
① ② ③
n-1 n-i-1 li[j]li[j]>li[j+1] 从左往右冒泡，升序排序
n-1,i,-1 li[j-1]li[j-1]>li[j] 从右往左冒泡，升序排序
n-1,0,-1 i li[j]li[j]>li[j+1] 从左往右冒泡，升序排序
n-1,n-i-1,-1 li[j]>li[j-1] 从右往左冒泡，降序排序
li[j]1.编写如下 Python 程序，对序列[9,2,4,6,7,8]进行冒泡排序：
a=[9,2,4,6,7,8]
c=0 #变量 c 记录数据比较的次数
for i in range(len(a)-1):
for j in range(len(a)-i-1):
c+=1
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
2.执行上述程序段后，变量 c 的值为 15，表示排序过程中数据一共要比较 15 次。但在第一轮冒泡结束后，序列 a 中的数字顺序变为[2,4,6,7,8,9]，已经有序排列，之后的比较无意义。
通法三　冒泡排序的优化
3. 基于以上问题可以对程序进行优化，当序列已经有序时结束排序。引入一个变量 flag，当排序进行到某一轮时若无数据交换，表示序列已经有序，根据 flag 的值结束循环，优化后代码如下：
a=[9,2,4,6,7,8]
flag=False
c=0
for i in range(len(a)-1):
flag=False
for j in range(len(a)-i-1):
c+=1
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
flag=True
if flag==False:
break
print(a)
#此时 c 的值为 9，程序执行效率大大提高
1.用冒泡排序对数据序列8，10，12，6，4，2进行从左往右的升序排序，第三趟排序后的状态是 （　　）
A.8，10，6，4，2，12
B.8，6，4，2，10，12
C.6，4，2，8，10，12
D.4，2，6，8，10，12
第一趟：8，10，6，4，2，12；第二趟：8，6，4，2，10，12；第三趟：6，4，2，8，10，12。
一、冒泡排序的原理
C
√
2.有一组数据序列35，61，30，85，99，6，67，现使用冒泡排序从左边开始对其进行升序排序，则数据的交换次数最少是 （　　）
A.19
B.7
C.6
D.9
数据交换的次数即是当两个相邻的元素中前一个的值比后一个的值大时进行交换，则第一趟排序时，交换61和30、99和6、99和67，共交换3次，得到数据序列是35，30，61，85，6，67，99；第二趟排序时，交换35和30、85和6、85和67，共交换3次，得到数据序列是30，35，61，6，67，85，99；第三趟排序时，交换61和6；第四趟排序时，交换35和6；第五趟排序时，交换30和6；交换次数最少是9次。
D
√
3.有如下Python程序段：
def bubbleSort(alist):
for num in range(len(alist)-1,0,-1):
for i in range(num):
if alist[i]>alist[i+1]:
alist[i],alist[i+1]=alist[i+1],alist[i]
alist=[67,26,55,90,31,85,43,56,28]
bubbleSort(alist)
print(alist)
执行该程序段后，输出的结果是 （　　）
A.[90,67,55,31,28,26,43,56,85]
B.[26,31,55,67,85,90,56,43,28]
C.[26,28,31,43,55,56,67,85,90]
D.[90,85,67,56,55,43,31,28,26]
C
√
变量num控制冒泡的次数，变量i控制冒泡的过程，num从列表中最后一位的下标开始到1结束（0取不到），内层for循环每轮进行num次比较，所以列表从第0位开始到第num-1位，都与其后一位比较，每一轮排序都会确定一个最大值在范围内最末尾，之后的循环范围逐次缩小，完成列表的升序排序。
二、冒泡排序的Python实现
4.有如下Python程序段：
import random
a=[0]*6
i=0
while i<=5:
a[i]=random.randint(1,10)
if a[i]%2==i%2:
i+=1
for i in range(0,2):
k=1
for j in range(0,4-i*2):
if a[j]*k>a[j+2]*k:
a[j],a[j+2]=a[j+2],a[j]
k=-k
执行该程序段后，列表a中各元素值不可能是 （　　）
A.[4,9,6,7,10,3]
B.[6,9,10,9,10,1]
C.[2,3,4,4,8,9]
D.[4,9,6,5,8,5]
C
√
该程序段的while循环生成的数据a[i]和索引i的奇偶性相同，for循环对数组a中奇偶位置的数据分别进行冒泡排序。当i=0、j=0时，比较的条件为a[0]>a[2]；当i=0、j=1时，比较的条件为a[1]a[4]，随后依次变化。最终实现偶数位置非降序排序，奇数位置非升序排序，根据上述分析结论检查四个选项，选项C中a[3]的值为4，不符合题意。
三、冒泡排序的变式
5.有如下Python程序段：
d=[1,7,5,2,3]
flag=False;last=i=c=0
while i<4 and flag==False:
flag=True
c+=1
for j in range(4,i,-1):
if d[j]d[j],d[j-1]=d[j-1],d[j]
flag=False;last=j
c+=1
i=last
执行该程序段后，变量c的值为 （　　）
A.6 B.7 C.8 D.9
该程序段对冒泡排序的范围和轮数进行优化。首先，变量flag起到一个轮数优化的作用，每一轮排序的开始初始化flag=True，若在该轮排序中发生交换，则flag置为False，说明数组d排序还未完成，否则说明数组d已经有序。其次，变量last起到一个范围优化的作用，用last记录最后一次交换的位置，下一遍冒泡冒到last位置即可。最后，用变量c统计交换次数与轮数的和，程序从后往前实现升序冒泡排序，交换次数为5次，且由于范围优化的存在，最后一次5和7交换后循环已经结束，共遍历了3遍，故变量c的值为5+3=8。
C
√
四、冒泡排序的优化
6.有如下Python程序段：
a=[1,2,5,5,6,7]
for i in range(5):
for j in range(5,i,-1):
if a[j]%2<=a[j-1]%2:
a[j],a[j-1]=a[j-1],a[j]
运行该程序段后，数组a的值是 (　　)
A.[6,2,5,5,7,1] B.[2,6,1,5,5,7]
C.[6,2,5,5,1,7] D.[2,6,1,7,5,5]
该程序段根据奇偶性进行排序，每轮排序从后往前，依次比较相邻元素，若为一奇一偶，则偶数要排在前面，当奇偶性一致时，也要进行交换。一轮排序结束后，缩小左侧排序范围，继续下一轮排序。对于数组a=[1,2,5,5,6,7]，第一轮排序得到a=[6,1,2,5,5,7]，第二轮排序得到a=[6,2,1,7,5,5]，第三轮排序得到a=[6,2,5,1,7,5]，第四轮排序得到a=[6,2,5,5,1,7]，最后一轮排序得到a=[6,2,5,5,7,1]。
A
√
7.有如下Python程序段：
a=[4,5,7,9,2,8]
for i in range(3):
for j in range(2,len(a)-i*2):
if a[j]a[j],a[j-2]=a[j-2],a[j]
执行该程序段后，a的值是 （　　）
A.[2,4,5,7,8,9] B.[9,8,7,5,4,2]
C.[4,5,7,2,8,9] D.[2,5,4,8,7,9]
D
当i为0时，j的取值为2～5，比较元素a[2]和a[0]、a[3]和a[1]、a[4]和a[2]、a[5]和a[3]的大小，若前者小于后者，则交换，得到a的值为[4,5,2,8,7,9]；当i为1时，j的取值为2～3，比较元素a[2]和a[0]、a[3]和a[1]的大小，若前者小于后者，则交换，得到a的值为[2,5,4,8,7,9]；当i为2时，j取不到值。故最终a的值为[2,5,4,8,7,9]。
√
8.［2026.1浙江选考］某算法的部分流程图如图所示，若n的值为8，数组元素a[0]至a[n-1]依次存放2,3,4,8,5,4,9,6，执行这部分流程后，输出c的值为 （　　）
A.1
B.2
C.3
D.4
D
该流程图的功能类似冒泡排序的单轮循环，由语句“a[i]√
i a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] c
7 2 3 4 8 5 4 6 9 7
6 2 3 4 8 5 4 6 9 7
5 2 3 4 8 4 5 6 9 5
4 2 3 4 4 8 5 6 9 4
3,2,1 2 3 4 4 8 5 6 9 4
0 输出c
9.定义如下函数：
def bbsort(data):
blk=[];st=0
for i in range(1,len(data)):
if data[i]!=data[i-1]:
ed=i-1
blk.append([st,ed])
st=i
for i in range(len(blk)):
for j in range(0,len(blk)-i-1):
if data[blk[j][0]]>data[blk[j+1][0]]:
blk[j],blk[j+1]=blk[j+1],blk[j]
若参数data为[2,2,2,1,1,3,3,3,3,7,7,7,4]，调用该函数后，blk[x][1]（0≤x≤len(blk)-1）的值不可能是 (　　)
A.2 B.4 C.11 D.12
D
√
该函数首先遍历data，找出元素连续重复的区间，将区间的起始和终点位置添加到列表blk中（注意：最后一个元素连续重复区间不会被添加）。然后通过比较data中所有起始位置的值，对blk中的元素进行排序。若参数data为[2,2,2,1,1,3,3,3,3,7,7,7,4]，调用该函数后，首先得到blk=[[0,2],[3,4],[5,8],[9,11]]，排序后得到blk=[[3,4],[0,2],[5,8],[9,11]]，故blk[x][1]（0≤x≤len(blk)-1）的值不可能是12。
10.有如下Python程序段：
a=[111,64,9,12,34,25,22]
for i in range( len(a)-1 ):　#①
for j in range( len(a)-i-1 ):　#②
if a[j]a[j],a[j+1]=a[j+1],a[j]
print(a)
下列关于该程序段的说法，不正确的是 （　　）
A.若将加框①处改为“2”，则程序运行结果不变
B.若将加框②处改为“len(a)-2,i-1,-1”，则总交换次数会发生改变
C.执行该程序段后，总比较次数为21次
D.执行该程序段后，输出的结果是[111,64,34,25,22,12,9]
B
该程序段为从左往右的降序冒泡排序，每轮将最小值交换到最右端，第1轮排序结果为[111,64,12,34,25,22,9]，第2轮排序结果为[111,64,34,25,22,12,9]，此时已经有序排列，因此若将加框①处改为“2”（表示执行2轮冒泡排序），则程序运行结果不变。若将加框②处改为“len(a)-2,i-1,-1”，则冒泡方向变为从右往左，但不会改变总交换次数。总比较次数=7×6/2=21。
√
11.［2025强基联盟］有如下Python程序段：
d=[27,78,25,36,5]
flag=True;i=0
while i<=3 and flag :　#①
flag=False
for j in range(len(d)-1,i,-1):
if d[j]>d[j-1] :　#②
d[j],d[j-1]=d[j-1],d[j]　#③
flag=True
i+=1
print(d)
执行该程序段后，下列说法不正确的是 （　　）
A.输出的结果是[78,36,27,25,5]
B.将加框①处语句改为“i<=2 and flag”，输出结果不变
C.加框②处语句执行的次数为9次
D.加框③处语句与加框②处语句的执行次数相同
该程序段对数组d中的元素从右往左进行比较，将较大值冒泡到左边，flag标记当前轮数据是否发生交换。若一轮排序后没有发生数据交换，则表明数组d已有序，提前结束排序，“i<=3”控制排序轮数最多为4轮。将加框①处语句改为“i<=2 and flag”，则表示最多排序3轮，而实际数组d经过2轮排序后已经有序，因此输出结果不变。加框②处语句执行的次数表示比较次数，第1轮比较4次，第2轮比较3次，第3轮比较2次，第3轮没有交换元素，结束排序，故共比较了9次。加框③处语句的执行次数表示交换次数，即数组d中逆序对的数量，共3对。
D
√
12.有如下Python程序段：
a=[5,2,6,4,9,8]
n=len(a);c=0
for i in range(1,n):
flag=True
c=c+1
for j in range(n-i):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]　#①
flag=False
if flag==True:
break
print(c)
下列关于该程序段的说法，正确的是 （　　）
A.该排序算法的时间复杂度是O(1)
B.第1轮冒泡后，数组a的值为[2,5,6,4,9,8]
C.执行该程序段后，输出c的值为2
D.①处语句共执行了4次
该排序算法是一个优化的冒泡排序，最优情况下时间复杂度为O(n)，最坏情况下时间复杂度为O(n2)。第1轮冒泡后，数组a的值为[2,5,4,6,8,9]。若一轮排序后没有发生数据交换，将提前结束排序，数组a经过2轮冒泡后已经有序，但第2轮发生了数据交换，因此还需要进行第3轮冒泡，故输出c的值是3。①处语句的执行次数即数据交换次数，等于数组a中的逆序对数，数组a中共有4对逆序数。
D
√
j=k
k=j+1
k+=1
j+=1
请回答下列问题：
（1）执行该程序段后，列表d的值是
　 　　　（单选）。
A.[15,54,43,12,77,87,54,22]
B.[12,15,22,43,54,54,77,87]
C.[15,12,43,22,77,87,54,54]
D.[87,77,54,54,43,22,15,12]
（2）请在画线处填入合适的代码。
13.在一个无序序列中同时存在偶数和奇数，小玲设计了一个算法，只对该序列中的奇数进行升序排序，且不移动偶数在序列中的位置，实现该算法的Python程序如下：
d=[43,54,77,12,15,87,54,22]
for i in range(len(d)):
j=0
while jif d[j]%2==1:
k=　　　①　　　1
while 　　　②　　　:
if d[k]%2==1:
if 　　　③　　　:
d[j],d[k]=d[k],d[j]
j+1
kA
√
d[j]>d[k]
（1）根据题目要求，结合代码可知，该程序是冒泡排序算法的变式，即在两两比较的过程中忽略偶数，只对列表中的奇数进行两两比较和交换，故执行该程序段后，列表d的值是[15,54,43,12,77,87,54,22]。　（2）①j表示的是两两比较中左边的元素索引，k表示被比较的元素索引，该元素要满足的特点是在j右边且为奇数，故k要在j右边一位开始查找，故初始位置为j+1。②处k在列表中查找，故不能超出列表最后一个索引值，故填入代码为kd[k]。
14.某村庄有若干条50米长的道路，每条道路的一边有5~10棵行道树，行道树的位置是随机不固定的。现工作人员需要补种两棵树，确定两棵树的位置的方法是：求出原本所有行道树之间的间距，找出最大的两个间距，将新的树种植在最大间距中间。例如，原有行道树的坐标为1，9，15，29，50，他们之间的间隔依次是8，6，14，21，故两棵新树应种植在第三棵树和第四棵树中间、第四棵树和第五棵树中间，位置是(15+29)/2=22、(29+50)/2=39.5。实现上述功能的Python程序如下：
请回答下列问题：
（1）若原本行道树的坐标为3，5，11，12，25，40，则两棵新树的栽种位置是
　　　　　　。
（2）程序画线①②处的语句分别是　　 　　（单选）。
A.①li[j]>li[j-1]　②li[j]B.①li[j]>li[j+1]　②li[j]C.①li[i]>li[j]　②li[i]D.①li[j]li[j+1]
（3）请在画线③④处填入合适的代码。
18.5和32.5
B
√
print("行道树的坐标是：",a)
dis=[]　#存储行道树的间隔
for i in range(len(a)-1):
dis.append(a[i+1]-a[i])
　　　③　　　　#将列表dis降序排序
point=[]　#存储新树的位置
for i in range(2):
for j in range(len(a)-1):
x=a[j+1]-a[j]
if x==dis[i]:
point.append(　　　④　　　)
break
print("新增树木的种植位置是：",point)
def sort_up(li):
for i in range(len(li)):
for j in range(len(li)-1-i):
if 　　　①　　　:
li[j],li[j+1]=li[j+1],li[j]
def sort_down(li):
for i in range(len(li)):
for j in range(len(li)-1-i):
if 　　　②　　　:
li[j],li[j+1]=li[j+1],li[j]
b=input("输入原有行道树的坐标：").split(",")
a=[int(i) for i in b]
sort_up(a)
sort_down(dis)
(a[j+1]+a[j])/2
（1）根据行道树的位置，可知间隔依次是2，6，1，13，15，间距值最大的是13和15，即第四棵树和第五棵树、第五棵树和第六棵树之间的间距，故新树的栽种位置是12和25的中间位置18.5，以及25和40的中间位置32.5。　（2）①程序sort_up()的作用是利用冒泡排序算法对列表进行升序排序，若当前比较的一位比后一位的值大，则交换两个元素的位置，故应该是li[j]>li[j+1]时交换。②sort_down()的作用是对列表进行降序排序，所以应在li[j]15.［2025嘉兴模拟］编写Python程序进行考生考场座位分配。每个考场共30个座位，座位编排时按如图a所示的顺序依次安排。将考生数据从如图b所示的Excel文件中导入到列表lst，格式如[["陈熙",3,30302,107],["邹瑜",1,30132,7],…]，每个元素包含考生姓名、班级、班级学号（年级+班级+班内学号）和序号共4个数据项，其中班级数≥6，班级人数在[30,50]范围内。
考生考场分配规则如下：
①按考场号从小到大、同一考场内按座位号从小到大安排考生座位。
②在所有班级中查找剩余未分配人数最多的班级（若存在并列情况，则选择查找到的第一个班级），然后从该班级的可分配考生中选取序号最小的考生排入当前座位。
③当前座位与前方、左方相邻座位的考生不能来自同一班级。例如，在安排8号座位时，若当前考生与前方的7号座位或左方的2号座位的考生来自同一班级，则需参照规则②从其他班级中重新选取。
（1）若仅对图b所示的7位考生进行考场分配，则根据分配规则，排在1号座位的考生的班级学号是　　　　　　　。
31338
（2）定义如下bub_sort函数，功能是对考生数据按照班级升序排序，班级相同时按序号升序排序。
def bub_sort(lst):
n=len(lst)
for i in range(n-1):
for j in range(n-1,i,-1):
if lst[j][1]lst[j],lst[j-1]=lst[j-1],lst[j]
画线处应填入的代码是
　　 　　（单选）。
A.lst[j][1]==lst[j-1][1] and lst[j][2]>
lst[j-1][2]
B.lst[j][1]==lst[j-1][1] and lst[j][2]<
lst[j-1][2]
C.lst[j][1]==lst[j-1][1] and lst[j][3]>
lst[j-1][3]
D.lst[j][1]==lst[j-1][1] and lst[j][3]<
lst[j-1][3]
D
√
（3）定义如下create_queinf函数，功能是对班级数据进行统计，结果保存在列表queinf中，queinf[0]用于保存班级数量，其余元素结构为[班级,起始位置,班级人数]。请在画线处填入合适的代码。
def create_queinf(lst):
queinf=[0]　#初始化
n=len(lst)
head=0
for i in range(1,n):
if lst[i-1][1]!=lst[i][1]:
queinf.append([lst[i-1][1],head,i-head])
　　　　　　　1
queinf.append([lst[i][1],head,n-head])
#queinf[0]保存班级数量
queinf[0]=len(queinf)-1　
return queinf
head=i
（4）定义如下check函数，功能是检查当前座位与前方、左方相邻座位的考生是否来自同一班级。请在画线处填入合适的代码。
def check(RoomID,SeatID,ClassID):
if SeatID%6!=0 and room[RoomID][SeatID-1]//100%100==ClassID:
return False
if 　　　　　　　 and room[RoomID][SeatID-6]//100%100==ClassID:
return False
return True
SeatID>5　或其他等价答案
（5）实现安排座位功能的部分Python程序如下，程序运行结果如图c所示，请在画线处填入合适的代码。
考场1：
座位号1：30601 座位号7：30805 座位号13：31330 座位号19：30603 座位号25：30102
座位号2：31222 座位号8：30606 座位号14：30837
座位号20：31205 座位号26：31037
座位号3：30622 座位号9：31203 座位号15：31338
座位号21：30630 座位号27：31408
座位号4：31211 座位号10：30618 座位号16：30836
座位号22：30536 座位号28：31001
座位号5：30636 座位号11：31201 座位号17：30541
座位号23：30839 座位号29：31420
座位号6：30834 座位号12：30504 座位号18：31208
座位号24：31314 座位号30：30104
def sel_sort(queinf):
#按各班学生数降序排序，代码略
def allocation(RoomID):
for i in range(30):
for j in range(1,queinf[0]+1):
if check(RoomID,i,queinf[j][0]):
m=j
break
room[RoomID][i]=　　　①　　　1
queinf[m][1]+=1
　　　②　　　1
if queinf[m][2]==0:
queinf[0]-=1
for i in range(m,len(queinf)-1):
if queinf[i][2]queinf[i],queinf[i+1]=queinf
[i+1],queinf[i]
lst[queinf[m][1]][2]　
或　lst[queinf[j][1]][2]
else:
break
if queinf[1][2]==0:
return
#主程序
#考生数据导入到列表lst，代码略
bub_sort(lst)
queinf=create_queinf(lst)
sel_sort(queinf)
#total存储需要的考场数量
total=(len(lst)-1)//30+1　
#初始化所有考场
room=[[""]*30 for j in range(total)]　
for i in range(total):
allocation(i)
#按序输出所有考场信息，代码略
queinf[m][2]-=1　
或　queinf[j][2]-=1
（1）图b所示的7名学生中，剩余未分配人数最多的班级为13班，该班级的可分配考生中序号最小为30，班级学号是31338，则排在1号座位考生的班级学号是31338。　（2）bub_sort(lst)函数对考生数据按照班级升序排序，班级相同时按序号升序排序，lst[j][1]表示班级，lst[j][3]表示序号，故填入代码为lst[j][1]==lst[j-1][1] and lst[j][3]5。　（5）①变量i枚举30个座位编号，变量j枚举所有班级的编号，判断编号为RoomID的考场中编号为i的座位是否满足规则③，若满足，则m记录当前的班级编号，退出内层循环。从该班级的可分配考生（对应班级数据存储在queinf[m]）中选取序号最小的考生（在lst中的位置为queinf[m][1]）排入当前座位，其班级学号在lst的第3列，故填入代码为lst[queinf[m][1]][2]。②m班的人数减少1，故填入代码为queinf[m][2]-=1。

展开更多......

收起↑