冒泡排序算法及程序实现一轮复习课件-2025-2026学年浙江省高三信息技术选择性必修一

冒泡排序算法及程序实现 1 知识过关 2 1. 冒泡排序的算法思想 冒泡排序是通过相邻元素的比较,将较小的数向上推移的排序技术。n个数需要通过n－1轮冒泡才能完成整个排序过程。 2. 冒泡排序的算法效率 对于n个元素的数组,共需要n－1遍加工,第一遍加工的比较次数为n－1次,第二遍加工的比较次数为n－2次,以此类推,最后一遍加工的比较只需1次。所以用冒泡排序算法进行排序时,总共的比较次数是: (n－1)+(n－2)+…+1=(次)。其时间复杂度为O(n2)。 3 3. 冒泡排序的核心代码(以升序排序为例,对列表a进行排序,也可以使用函数形式) (1)从后往前,小数往前冒。 　　n=len(a) 　　for i in range(1,n): 　　　　for j in range(n－1,i－1,－1): 　　　　　　if a[j－1]>a[j]: 　　　　　　　a[j],a[j－1]=a[j－1],a[j] (2)从前往后,大数向后沉(变形)。 　　n=len(a) 　　for i in range(1,n): 　　　　for j in range(0,n－i): 　　　　　　if a[j]>a[j+1]: 　　　　　　　a[j],a[j+1]=a[j+1],a[j] 4 4. 冒泡排序的优化 冒泡排序中,若在某一遍排序的过程中未发生数据交换,则意味着数据已经有序,可以直接结束该冒泡排序。利用该特性,可以优化冒泡排序的程序代码(参考例4)。 5 典例精选 6 【例1】 (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 【解析】 本题考查冒泡排序算法思想。已知外循环变量i的取值范围是[1,6]。当第一轮比较(i为1)时,内循环变量j的取值范围是[1,5],由于参与比较的两元素下标分别是j和j－1,故列表中仅元素s[0]~s[5]从前向后进行比较。再观察分支语句条件s[j]> s[j － 1]可知,当后一个数大于前一个数时要发生交换,故最终排序结果是降序。A正确。 【例2】 有如下Python程序段: k = 1 for i in range(0,len(a)－1): 　　if k*a[i] >k*a[i+1]: 　　　　a[i],a[i+1] = a[i+1],a[i] 　　k=－k 若列表a有7个元素,运行该程序后,a可能的值是(　　) A. [7,8,5,9,6,9,7] B. [7,6,5,8,7,9,9] C. [8,6,7,5,9,7,9] D. [7,8,6,5,7,9,9] A 【解析】 本题考查冒泡排序知识。程序中,当i的值为偶数时k=1,i的值为奇数时k=－1,k的值依次为1、－1、1、－1……交替变换。由条件“k * a[i]> k * a[i + 1]”可知,当k=1时,程序运行后满足a[i]<=a[i + 1];当k=－1时,程序运行后满足a[i]>=a[i + 1]。程序运行后,对于列表a中的数据,满足索引值为偶数的数值必定小于等于其下一个相邻数值,索引值为奇数的数值必定大于等于其下一个相邻数值。A正确。 【例3】 随机生成n个范围是[10,59]的不重复随机整数,并用冒泡排序将其升序排列后输出。Python代码如下,运行界面如图所示。 import random a=[0]*10 b=[False]*100 i=0 while i<=9: 　　　x=random.randint(10,59) 　　　while _______________:  　　　　　　x=random.randint(10,59) 　　　a[i]=x 　　　b[x]=True 　　　i=i+1 print(a) def bub_sort(d): 　　　n=len(d) 　　　for i in range :　　　　　　　#① 　　　　　　for j in range :　　 #② 　　　　　　　　　if d[j]>d[j+1]: 　　　　　　　　　　　　　d[j],d[j+1]=d[j+1],d[j] bub_sort(a) print(a) [10,16,15,50,30,26,13,23,47,54] [10,13,15,16,23,26,30,47,50,54] b[x]==True (1,n) (0,n－i) 请回答下列问题: (1)请在画线处填入合适的代码。 (2)加框处①的代码能否修改为(0,n－1)或(n－1,0,－1)?__________  (3)加框处②的代码能否修改为(n－i－1,－1,－1)?__________  【解析】 (1)此处考查不重复随机数知识。列表b用于标记列表a中的数是否已经存在,False表示没有,True表示已经存在,因此若b[x]的值为True,则表示列表a中已经存在x,该值必须重新生成。(2)冒泡排序的外循环用于控制冒泡的遍数(轮数),n个数据,只需冒泡n－1轮即可实现有序排列,因此可以修改为(0,n－1)或(n－1,0,－1)。(3)冒泡排序具有方向性,而内循环主要用于控制冒泡的方向,而冒泡的方向不能简单地换方向,因此不能改为(n－i－1,－1,－1)。 能 不能 【例4】 n个数据的冒泡排序需要经过n－1遍加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面。小刘发现,当某一遍加工过程中没有数据交换,说明数据已经有序,无须进一步加工。为此,小刘对算法进行优化,编写了一个Python程序,功能如下:运行程序时,在列表中显示排序前数据,然后在列表中显示这些数据按升序排序后的结果,最后显示排序过程的加工遍数。运行效果如图所示。 [30,18,49,67,69,36,88,21] [18,21,30,36,49,67,69,88] 排序过程的加工遍数为:3 实现上述功能的代码如下。其中加框处的代码有错误,请改正。 import random a=[0]*8 i=0 while i<=7: 　　　x=random.randint(10,99) 　　　a[i]=x 　　　i=i+1 print(a) n=len(a) i=1;flag=True while i<=n－1 or flag=True :　　　　　　　　#改错① 　　　flag=False 　　　for j in range(n－1,i－1,－1): 　　　　　if a[j－1]>a[j]: 　　　　 　　a[j],a[j－1]=a[j－1],a[j] 　　　　 　　flag=True 　　　i+=1 print(a) print("排序过程的加工遍数为:", str(i) )　　 #改错② (1)加框处①的代码改为____________________________。  (2)加框处②的代码改为__________。  i<=n－1 and flag==True str(i－1) 【解析】 本题考查冒泡排序的优化。冒泡排序可以进行优化,例如在某一轮冒泡中,没有数据交换,则意味着下一轮冒泡不需要继续进行,可以结束。①两个条件缺一不可,故应该是and。②外循环变量i从1开始,若本轮没有数据交换,则flag的值为False,此时i还要加1以后才能退出,因此共进行i－1轮冒泡排序,故答案是str(i－1)。 自我检测 16 1. 对5名学生按身高数据序列从低到高进行冒泡排序,第一遍加工后的结果为 “165,172,177,168,180”,则排序前这5名学生的身高数据序列不. 可. 能. 是(　　) A. 172,177,165,168,180　　 B. 172,177,168,165,180 C. 172,165,177,168,180　　 D. 172,177,168,180,165 【解析】 本题要求以升序冒泡排序第一遍加工后的结果为依据,判定原始数据序列的可能情况。以升序冒泡排序C中数据,第一遍加工后的结果应该为“165,172,168,177,180”,C符合题意。 C 17 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 【解析】 本题考查对冒泡排序算法基本思想的理解。冒泡排序算法有从前(左)向后(右)和从后(右)向前(左)之分,还有升序和降序之分,且每一轮排序结束后必有一个数被调整到正确位置。由第一轮排序的结果是“2,8,3,9,5,6,7”可知,最小值2处于最前面的正确位置,即此冒泡排序实现从后(右)向前(左)的升序。由此推断,A、B、C的一轮排序结果均不符合题意。“8,3,2,9,6,5,7”的一轮排序结果为“2,8,3,5,9,6,7”,D符合题意。 D 18 3. 对10个数据进行冒泡排序,需要比较的次数是(　　) A. 90 B. 110 C. 45 B. 55 【解析】 本题求规模为10的数据进行冒泡排序的比较次数。根据冒泡排序算法比较次数的计算方法可知,当n=10时,比较次数=10×(10－1)/2=45,C正确。 C 19 必备知识练 20 1. 采用冒泡排序算法对9个数据进行升序排序,则排序共需要进行的轮(遍)数是(　　) A. 1 B. 8 C. 9 D. 10 【解析】 n个数据共需要进行n－1轮(遍)冒泡才能实现有序,B正确。 B 21 2. 对7个数据采用冒泡排序算法进行升序排序,第一遍加工后的结果为1,70,53,57,28, 30,77,则原始数据可能是(　　) A. 1,70,53,57,77,28,30 B. 70,1,53,57,28,30,77 C. 70,53,57,28,30,77,1 D. 70,53,1,57,28,30,77 【解析】 本题给出7个数据采用冒泡排序第一遍加工后的结果来判定原始数据的可能情况。由于原始数据的情况可能不唯一。所以本题适合采用排除法来解决。选项A、B、D如果是原始数据,采用冒泡排序第一遍加工后的结果分别是“1,28,70,53,57,77,30” “1,70,28,53,57,30,77”和“1,70,53,28,57,30,77”,均不符合题意,而选项C通过冒泡升序排序第1遍加工后的结果如题意所述,符合题意。 C 22 3. 对3,7,5,8,2,6,14,12,13,21这10个数据进行从小到大的冒泡排序,第一遍加工需要进行的数据交换次数是(　　) A. 5 B. 6 C. 7 D. 8 【解析】 本题给出待排序的10个数据,并采用冒泡排序进行从小到大排序,要求统计第一遍加工数据的比较和交换次数。根据冒泡排序思想,在比较中,如果发生逆序现象,就需要发生交换。经过模拟发现第一轮冒泡中,发生数据交换5次。A正确。 A 23 4. 有如下Python程序: a= [19, 4, 1, 0, 2, 1, 9, 3] cnt=0 n=len(a) for i in range(n－1): 　　flag=False 　　for j in range(n－i－1): 　　　　if a[j]>a[j＋1]: 　　　　　　a[j],a[j＋1]=a[j＋1],a[j] 　　　　　　flag=True 　　cnt＋=1 　　if not flag: 　　　　break print(cnt) 则程序运行结束后,变量cnt的值为(　　) A. 3 B. 4 C. 5 D. 7 B 24 【解析】 本题考查冒泡排序的改进算法。在每一轮冒泡排序中,若未发生交换,则标记flag为false,提前结束冒泡排序,cnt用于记录总共进行的轮数。根据题意,第一轮冒泡排序结果为[4, 1, 0, 2, 1, 9, 3, 19],发生过交换,cnt=1;第2轮冒泡排序结果为[1, 0, 2, 1, 4, 3, 9, 19],发生过交换,cnt=2;第3轮冒泡排序结果为[0, 1, 1, 2, 3, 4, 9, 19],虽然此时冒泡排序结果已经有序,但是发生过交换,cnt=3,还需进行第4轮冒泡排序,结果依旧为[0, 1, 1, 2, 3, 4, 9, 19], cnt=4,这一轮没有发生交换,冒泡排序结束。 B正确。 5. 某冒泡排序算法的Python程序段如下: a = [66,34,12,59,21,26,18,45,20,16] for i in range(1,3): 　　for j in range(len(a)－1, i, －1): 　　　　if a[j] < a[j－1]: 　　　　　　a[j],a[j－1]= a[j－1],a[j] 执行该程序段后,列表a中的值为(　　) A. [66, 59, 45, 34, 12, 26, 21, 20, 18, 16] B. [66, 12, 16, 34, 18, 59, 21, 26, 20, 45] C. [12, 16, 18, 20, 21, 26, 21, 20, 18, 16] D. [12, 16, 18, 66, 34, 20, 59, 21, 26, 45] 【解析】 本题考查冒泡排序算法。根据内循环的判断条件可知,数据按照从小到大,且上冒的排列。但由于外层循环变量i从1开始,因此数据a[0]未参与排序。第一轮排序后a=[66, 12, 34, 16, 59, 21, 26, 18, 45, 20],第二轮排序后a=[66, 12, 16, 34, 18, 59, 21, 26, 20, 45]。B正确。 B 26 6. 有如下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＋1]: 　　　　　　a[j],a[j＋1]=a[j＋1],a[j] print(a) 下列说法中,错. 误. 的是(　　) A. 若①加框处改为“2”,程序运行结果不变 B. 若②加框处改为“len(a)－2,i－1,－1”,总交换次数会发生变化 C. 该程序执行结束后,总的比较次数为21 D. 该程序执行结束后,数组a结果为[111,64,34,25,22,12,9] B 27 【解析】 本题考查冒泡排序算法知识。根据给出的数据以及冒泡方向,两遍即可完成,所以改为2,结果不变,A不符合题意。冒泡排序的交换次数和逆序对有关,和冒泡方向无关,B符合题意。比较次数为1＋2＋3＋4＋5＋6=21,C不符合题意。本题代码是降序,结果正确,D不符合题意。 7. 有如下Python程序段: import random a=[54,36,69,11,3,46] t=(random.randint(1,3))*2 for i in range(6－t): 　　for j in range(5,i,－1): 　　　　if a[j]<a[j－1]: 　　　　　　t=a[j] 　　　　　　a[j]=a[j－1] 　　　　　　a[j－1]=t print(a) 执行该程序段后,输出的结果不. 可. 能. 是(　　) A. [3,11,36,46,54,69] B. [3,11,54,36,69,46] C. [3,54,36,69,11,46] D. [54,36,69,11,3,46] 【解析】 首先t是一个[2,6]之间的随机偶数,即[2,4,6], C选项的结果是冒泡排序一趟后的结果,就是t=1时才能有的结果,所以不可能,C符合题意。 C 29 关键能力练 30 8. 有如下Python程序段: a = ["Java ", "VB ", "Delphi ", "Pascal ", "Python ", "C "] for i in range(0,3): 　　for j in range(0,5－i): 　　　　if a[j] > a[j ＋ 1]: 　　　　　　　　a[j],a[j＋1] = a[j＋1],a[j] print(a) 执行该程序段后,列表元素a的数据为(　　) A. ["C ", "Delphi ","Java " , "Pascal ", "Python ", "VB "] B. ["Delphi ", "Java ", "C ", "Pascal ", "Python ", "VB "] C. ["VB ", "Python ", "Pascal ", "Java ", "Delphi ", "C "] D. ["VB ", "Python ", "Pascal ", "C ", "Java ", "Delphi "] B 31 【解析】 本题考查冒泡排序。由代码可知,冒泡进行3次,将最大的值往后推,由于是字符串的比较,先比较每个单词的首字母,若相同则比较第二个字符,ASCII码值大的为大。因此列表中,后三个数据肯定是最大的三个值,模拟后结果是B。B正确。 9. 有如下Python程序段: import random a=[0]*6 i = 0 while i<= 5: 　　a[i] = int(random.random()* 10)＋ 1 　　if a[i] % 2 == i % 2: 　　　　　i=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 33 执行该程序段后,列表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 ] 【解析】 本题考查冒泡排序的变形。在生成列表元素阶段,奇数位是奇数,偶数位肯定是偶数。代码中k值在1和－1间摆动,奇数位和奇数位单独进行排序,排序后偶数位升序,奇数位降序。而选项C中全部都是升序,且奇偶性也不对,所以不可能,C符合题意。 C 10. 如下Python程序段实现对数组元素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－1]:　#语句② 　　　　　　a[j],a[j－1]=a[j－1],a[j] #语句③ 　　　　　　last=j 　　start=last print(a) 35 下列关于运行该程序段后的说法,错. 误. 的是(　　) A. 加框处代码第一次执行结束后，start的值为3 B. 语句①可以修改为while start<n－1: C. 语句②执行了6次 D. 语句③执行了3次 【解析】 本题考查冒泡排序以及相关优化。根据数组a的元素,第一遍冒泡过程,最后交换的是42和53,此时j=4,A不符合题意。根据代码,start的最大取值为n－1,所以这两个条件等价,B不符合题意。循环语句执行了2遍,第一遍if语句执行了5(5－>1)次,第二遍2(5－>4)次,共7次,C符合题意。数组a中只有3对逆序对,所以交换语句执行3次,D不符合题意。 C 11. 生成n个随机整数,并用优化的冒泡排序将其升序排列后输出。实现上述功能的Python代码如下,运行界面如图所示。请在画线处填入合适的代码。 #生成n个不重复的随机整数并赋值给列表a,代码略 def bub_sort(d): 　　①______________  　　i=0 　　while i<=n－1: 　　　　　k=i;i=n 　　　　　for j in range(n－1,k,－1): 　　　　　　　if d[j－1]>d[j]: 　　　　　　　　　　d[j],d[j－1]=d[j－1],d[j] 　　　　　　　　　　②__________   bub_sort(a) print(a) [28,83,93,38,37,44,59,86,68,14] [14,28,37,38,44,59,68,83,86,93] n=len(d) i=j 37 【解析】 本题考查冒泡排序的优化。①结合代码上下文,此处需要n的初始化,根据逻辑可知,应该是列表d的长度。②冒泡排序可以进行优化,例如在某一轮冒泡中,没有数据交换,则意味着下一轮冒泡不需要继续进行,可以结束。考虑到最后发生数据交换的位置是 d[j－1]和d[j],因此有序区应该是d[0]至d[j－1],从d[j]开始后面的是无序区,下一趟排序的数据区域缩小为[j,n－1]即可。故答案为i=j。 12. 小张从网上获取了2022年北京冬奥会奖牌榜数据,如图所示。要求输出金牌数最高的10个国家或地区，并按金牌数降序排序,若金牌数相同,则按银牌数降序排序。为实现上述功能,小张编写了如下Python程序。请回答下列问题: (1)请在画线处填入合适的代码。 (2)加框处的代码有错误,请改正。 【答案】 a[j][1]>a[j－1][1]or a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2]a=[] 39 f=open("2022冬奥会奖牌榜.txt",ˈrˈ,encoding=ˈUTF－8ˈ) flag=True for line in f.readlines(): 　　if flag: 　#处理首行标题数据 　　　　print(line) 　　　　①_______________  　　else: 　　　　t=line.split(ˈ,ˈ) 　　　　for i in range(1,len(t)): 　　　　　　t[i]=int(t[i]) 　　　　a.append(t) print("冒泡排序:") n=len(a) for i in range(10): 　　for j in ②___________________:  　　　　if a[j][1]>a[j－1][1] : 　　　　　　a[j],a[j－1]=a[j－1],a[j] for i in range(10): 　　print(a[i]) flag=False range(n－1,i,－1) 【解析】 (1)①flag为True时,需要处理首行标题,之后flag置为False,后续数据进入else分支处理,因此此处填flag=False。②根据冒泡排序的核心程序,外层循环控制冒泡的遍数,本题控制排序进行10遍(只需要排名前10的数据),每一遍排序都有一个元素有序,而内层循环控制冒泡排序的范围,由于a[j]需要与前一个元素a[j－1]比较,金牌数多的前移,可见该冒泡排序为从后往前的按金牌数降序冒泡排序,因此j的范围是[n－1,i＋1]闭区间,步长为－1,因此此处填range(n－1,i,－1)。(2)要求按照金牌数进行降序排序,在金牌相等的情况下,再按照银牌数降序排序,因此冒泡排序时,有两种情况需要交换元素位置:①a[j][1]>a[j－1][1],即后一个元素的金牌数比前一个元素的金牌数多;②a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2],即后一个元素的金牌数与前一个元素的金牌数相等,但是后一个元素的银牌更多。 13. 小王基于冒泡排序的思想设计了一个排序算法。先生成n个1~99之间的随机整数,然后用冒泡算法将列表中奇数位置的元素按照升序、偶数位置的元素按照降序分别进行排序。实现上述功能的Python程序代码如下,请回答下列问题: 原始数据是:[21,13,96,23,66,58,64,48,6,14] 排序后数据:[6,58,21,48,64,23,66,14,96,13] (1)请在画线处填入合适的代码。 (2)将加框处的代码修改为“(n－1)//2＋1”,程序功能__________(填“会”或“不会”)发生改变。  不会 42 import random n=10 a=[random.randint(1,99)for i in range(n)] print("原始数据是:",a) for i in range(0, (n－1)//2 ): 　　k=1 　　for j in range(0,n－i*2－2): 　　　　if k*a[j]>k*a[j＋2]: 　　　　　　a[j], a[j＋2] = ①________________  　　　　②__________  print("排序后数据:",a) a[j＋2], a[j] k=－k 【解析】 本题考查冒泡排序算法的变形。(1)①根据代码可知,此处是将a[j]和a[j＋2]两个元素进行交换。②奇数位和偶数位升序和降序要实现交替进行,不等式变向,需要通过k实现,因此k的值必须在1和－1两者之间交替变化,因此k=－k。(2)冒泡排序中,外循环增加一次,不影响程序的功能。 14. 双向冒泡排序:经典冒泡排序是单向的,始终从第一个(或最后一个)元素开始扫描。小王对冒泡排序进行了改进,从两端进行扫描,首先从数组的左端到右端进行扫描,把最大的数往后交换(以升序为例),再从右端往左端扫描,把最小的数往前交换,多次扫描后,得到一个有序的序列。于是定义了left和right两个指针,每一遍排序,left右移一位,right左移一位。一趟排序,将最大值下沉到最后一位,最小值上浮到最前一位,最终使整个数组有序。运行界面如图所示,实现上述功能的Python代码如下。请回答下列问题: 排序前数据:[73,21,98,49,96,82,99,14,48,92] 排序后数据:[14,21,48,49,73,82,92,96,98,99] 45 (1)请在画线处填入合适的代码。 (2)加框处代码有错误,请改正。 import random n = 10 a = [random.randint(10,99)for i in range(n)] print("排序前数据:",a) left,right = 0,n－1 while left<right: 　for j in range(①_______________):  　　if a[j]>a[j＋1]: 　　　 a[j],a[j＋1]=a[j＋1],a[j] 　right－=1 　for j in range(②__________________):  　　if a[j]>a[j－1] : 　　　 a[j],a[j－1]=a[j－1],a[j] 　③______________  print("排序后数据:",a) 【答案】 a[j]<a[j－1] left, right right,left,－1 left＋=1 【解析】 本题考查双向冒泡排序。(1)left和right分别扫描的左右边界,有序区位于左右两端,每次扫描后,无序区边界缩小,因此left每次加1,而right每次减1。(2)升序排序,故代码为a[j]<a[j－1]。 15. 某大学演唱会以评委投票方式评选最优秀的歌曲,每张选票仅填一个作品编号,得票数过半的作品获“最佳作品奖”。小李同学和小王同学负责收集全部选票,其中小李同学已将收集的选票按作品编号升序排序,小王同学收集的选票未排序。现要求将全部选票按作品编号进行非降序排序,找出获“最佳作品奖”的作品编号。编写程序,实现上述功能。运行程序,在数组a中存储全部选票,小李收集的选票在前,小王收集的选票在后。先按作品编号对全部选票进行非降序排序,最后找出“最佳作品奖”的作品编号并输出显示。运行结果如图所示,请回答下列问题: 48 (1)实现上述功能的部分程序如下,请在画线处填入合适的代码。 (2)程序中加框处的代码有错误,请改正。 【答案】 (0,n//2＋1) # m为一常数 #将n张选票的作品编号存入列表a,a[0]~a[m－1]、a[m]~a[n－1]分别为小李同学和小王同学#收集选票的作品编号,代码略 n=len(a) c=[""]*n for i in range(n,m,－1): 　　for j in ①_____________________________________________________:  　　　　if a[j＋1] < a[j]: 　　　　　　a[j],a[j＋1] = a[j＋1],a[j] i=0 ②__________  for k in range(0,n): 　　if j > n－1 or ③___________________________________________:  　　　　c[k] = a[i]; i = i ＋ 1 　　else: 　　　　c[k] = a[j]; j = j ＋ 1 for i in range(0,n//2): 　　if c[i] == c[i ＋ n // 2]: 　　　　print(c[i]) 　　　　break range (m,n－2)或 range (m,i－1) 或 range (n－2,m－1,－1) j=m i<m and a[i]<=a[j]或 i<m and a[i]<a[j] 【解析】 本题考查冒泡排序及归并排序知识。(1)①考虑到冒泡排序的边界条件及外循环的范围,答案如上。②由代码可知,j是小王同学的数据范围,故j=m。③把列表a中两段合并成有序结果,利用双指针策略有序放置于列表c中,使用了归并排序的策略。初始时i指向第一段数据的起始位置1,j指向第二段数据的起始位置m。可知,i的取值范围为1~m－1,j的取值范围为m~n－1,当我们控制两个指针移动时,需要注意i、j的取值区间,避免越界。因此答案是i<m and a[i]<=a[j]。(2)改错处所在程序段用于输出最佳作品的作品编号,根据题意:得票数过半的获最佳作品奖,所以只要遍历一半的数据,当第i个数据和第(i＋一半)的数据都为该选票时,输出该作品编号,此处主要考虑奇数张选票时,该如何选取范围,可以举例,快速确定正确的范围,例如共有7张选票,枚举至第4张时才能完全确定。考虑n的奇偶性,所以正确答案为(0,n//2＋1)。 16. 小王为了挑选出符合自己要求的相机,从某电商平台上获取了相关产品的一系列数据,数据格式如图所示。在挑选过程中,他的第一考虑要素是价格实惠,而对于价格相同的,他的次要考虑因素是销售量。现请你帮助他实现下列排序和筛选过程:按照商品价格升序排序,商品价格相同的,根据销售量进行降序排序,在排序的过程中对数据进行整理,剔除重复数据。 51 (1)根据题中的算法描述,结合程序代码分析,将商品价格和销售量按题目要求采用的算 法是___________(填“选择排序”或“冒泡排序”),其时间复杂度为__________(单选,填字母)。  A. O(n)/ B. O(log2n)/ C. O(n2)) 冒泡排序 C 52 (2)请在画线处填入合适的代码。 import csv a=[] f=open("camera.csv","r") reader=csv.reader(f) for item in reader:　#读取文件添加到列表a中 　　a.append(item) f.close() n=len(a) for i in range(1,n):　#将列表a中的“销售量”和“价格”转换为整型数据 　　a[i][2]=int(a[i][2]) 　　a[i][3]=int(a[i][3]) i=1; m=n－1 while i<n: 　for j in range(①_____________):  　　　if ②______________________________________________________________:  　　　　　a[j],a[j－1]=a[j－1],a[j] 　　　elif a[j]==a[j－1]: 　　　　　③______________  　　　　　m－=1 　i＋=1 for i in range (m＋1): 　　print (a[i]) m, i, －1 a[j][3]<a[j－1][3]or a[j][3]==a[j－1][3]and a[j][2]>a[j－1][2] a[j]=a[m] 53 (3)按照上述要求排序后,小王希望筛选出每档售价的销售量的前两名的产品数据。加框处的代码有错误,请改正。 def sx(x,y): 　　if　y－x＋1>2 :　　　　#① 　　　　print(a[x]) 　　　　print(a[x＋1]) 　　else: 　　　　print(a[x]) i=0 j=0 for i in range(1,m): 　　if a[i][3]==a[i－1][3] :　　#② 　　　　sx(j,i－1) 　　　　j=i sx(j,i－1) 【答案】 ①y－x＋1>=2或y－x>=1　②a[j][3]==a[i－1][3] 54 【解析】 本题考查多条件冒泡排序和程序实现过程。(1)从排序代码可知,比较和交换的是相邻的元素,属于冒泡排序算法。根据代码双重循环可知,其时间复杂度为O(n2),C正确。(2)①根据代码“a[j],a[j－1]=a[j－1],a[j]”可知,该程序实现从后往前的冒泡排序,所以①处填入的代码为m, i, －1。②排序的首要关键字为商品价格升序,次要关键字为销售量降序,所以此处填入的代码为a[j][3]<a[j－1][3]or a[j][3]==a[j－1][3]and a[j][2]>a[j－1][2]。③该部分实现去重功能,当a[j]=a[j－1]时,用当前队尾元素a[m]覆盖a[j],以实现删除a[j]的功能,同时更新对尾指针m。(3)①题目要求筛选出“每档售价销售量前两名”,所以应填入的代码为y－x＋1>=2,当前代码实现的功能是当每档售价销售量存在3个及以上时才进行输出,不符合题目要求。②由后面的代码可知,应该是j和i－1的两个价格进行比较。 55 $