资源简介

课时28　冒泡排序算法
【学业要求】
知识点 学业水平等级
1.从相邻数据比较和交换的本质理解冒泡排序的算法思想。 4
2.通过对内、外循环和比较语句的功能,用程序代码实现冒泡排序。 4
　　冒泡排序算法是迭代算法思想的重要体现,排序的趟数决定了迭代的次数,因此明确迭代的对象以及迭代后的结果是本节课的重要内容。在2023年6月卷中,考查了排序(迭代)的范围以及排序的过程,要求学生掌握排序后的结果。
(2023年6月浙江选考)列表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控制排序趟数。内循环变量j取值范围是[1,5],条件s[j]>s[j-1]表示当后一个数大于前一个数时要发生交换,实现降序排列。参加排序元素仅s[0]~s[5]。
1.　　　　(sorting)是使系列中的元素按照某个字段的值递增(或递减)的次序重新排列的操作。在排序的过程中,元素的值保持不变,但其在系列中的顺序可能会改变。
2.待排序的数据存储方式一般有　　　　和链表两种方式,利用数组存储数据,在排序时需要对数据本身进行物理重排,可能需要移动数据的位置,而利用链表存储数据,只需要修改指针即可。
3.常见的排序算法有　　　　排序、选择排序、插入排序、快速排序、堆排序、归并排序、桶排序等。在选择排序的算法时,可以根据待排序数据自身的特点来选择相应的算法。
4.冒泡排序(Bubble_Sort)是在一系列数据中对　　　　两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
5.冒泡排序算法把待排序的n个元素的数组看成垂直堆放的一列数据,对相邻两个数据进行比较,将较　　　　的数据换到上面的一个元素中(升序)。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。当第一遍加工完成时,最小的数据已经“上浮”到第一个元素的位置(升序)。然后对余下的n-1个元素重复上述处理过程,直到最后进行余下两个数据的比较和交换。
6.对于n个元素的数组,共需要　　　　遍加工,第一遍加工的比较次数为　　　　次,第二遍加工的比较次数为n-2次,以此类推,最后一遍加工的比较只需　　　　次。所以用冒泡排序算法进行排序时,共需比较n(n-1)/2(次)。其时间复杂度为　　　　。
自我校对:1.排序　2.数组　3.冒泡　4.相邻　5.小
6.n-1　n-1　1　O(n2)
【典例1】 采用冒泡排序算法对某数据序列进行排序,第一轮排序后的结果是“2,8,6,3,5,7,9”,则第二轮排序需要交换的次数为(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
思维点拨
明考向 本题考查冒泡排序算法的算法思想
精点拨 由第一轮数据“2,8,6,3,5,7,9”可知,采用冒泡排序对数据进行升序排序,但有两种可能,一种是从后往前的冒泡升序,则第二轮排序后的数据为“2,3,8,6,5,7,9”,交换2次,另一种是从前往后的冒泡升序,则第二轮排序后的数据为“2,6,3,5,7,8,9”,交换4次
答案　A
【变式1】 采用冒泡排序算法对数据序列“22,35,43,56,19,8”完成升序排序,需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.21次
答案　A
解析　本题考查冒泡排序算法的算法思想。找出各个逆序对。比22小且在右侧的数有19和8共2个。同理比35、43和56小且在右侧的数各有2个。比19小的数有1个。一共有9对逆序对。
【典例2】 列表s包含8个互不相等的元素,即s[0],s[1],s[2],...s[7],有如下Python程序段:
n=8
for i in range(1,5):
　for j in range(n-2,i,-1):
　　 if s[j]　　　　s[j],s[j+1]=s[j+1],s[j]
该程序段实现的是(　　)
A.s[0]到 s[3]的升序排列
B.s[4]到 s[7]的升序排列
C.s[2]到 s[5]的降序排列
D.s[1]到 s[4]的降序排列
思维点拨
明考向 本题考查冒泡排序算法实现
精点拨 从后往前冒泡,前面的数据先有序,有序区间的左端点是i+1,比较对象是s[j]答案　C
【变式2】 互不相等的10个列表元素s[0]、s[1]、s[2]……s[9],有如下Python程序段:
n=10
for i in range(5):
　for j in range(1,n-i):
　　 if s[j]>s[j-1]:
　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到 s[5]的降序排列
B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列
D.s[5]到 s[9]的升序排列
答案　C
解析　本题考查冒泡排序算法思想。分析冒泡排序内循环的代码,是从左(前)向右(后)冒泡、降序。外循环只进行了5次,所以只有最后5个数(s[5]到 s[9])是有序的。
【典例3】 n名考生的考号和成绩保存在数组cj中,如[["230101",98],["230109",97]……],现要按成绩从高到低录取k(kfor i in range(n-1):
　for j in range(①　　　　):
　　 if cj[j][1]>cj[j-1][1]:
　　　　cj[j],cj[j-1]=cj[j-1],cj[j]
　if ②　　　　 and cj[i][1]!=cj[i-1][1]:
　　 break
print("录取考生的考号有:")
for j in range(③　　　　):
　print(cj[j][0],end=" ")
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 ①排序的方向和区间。成绩从高到低录取考生,需进行降序排列,实现前面的数据先有序,因此需从后往前冒泡。第i趟排序实现前面第i位置数据有序,因此第1次比较位置n-1和n-2,最后1次比较位置i和i+1,j的终值为i+1,步长为-1,但range是一个左闭右开的区间。②最后一名成绩相同者均可进入面试,因此结束排序的条件有两个,就是i的值大于等于k且他与前面的成绩不相等。③找到第1个不符合条件学生的索引为i,因此只需输出索引为0至i-1的学生考号
答案　①n-1,i,-1　②i>=k　③i
【变式3】 有如下Python程序段:
L=[21,12,13,17,16,15,20,28,11]
def shengxu(a,b):
　for i in range(0,b-a):
　　 for j in range(　　　　　 ):
　　　 if L[j]>L[j+1]:
　　　　　L[j],L[j+1]=L[j+1],L[j]
shengxu(3,7)
print(L)
若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为(　　)
A.i,b B.0,b- i
C.a,b-i D.b-1,a-i-1,-1
答案　C
解析　本题考查冒泡排序的算法实现。外循环控制排序的次数,也与排序的区间位置有关。冒泡排序必须是一端固定,另一端随着排序的过程将不断地缩短。若从前往后冒泡,则排序的初值必须为a,第一趟排序的区间是最长的,此时i的值为0,最后位置为b,而j+1到过b时,j的值为b-1,若要取到b-1,则终值必须为b,结合i的值,终值为b-i。
　　排序往往先找出一列数中的最值,将这个最值交换到该列数的末端,把数列划分为有序区间和无序区间,把这个操作称为一趟排序。再对无序区间进行重复操作,不断地扩大有序区间,缩小无序区间,当无序区间中只有一个数据时,全部数据有序,结束排序。冒泡排序基本算法思想是每次总是从最左边或最右边的位置(开始位置是固定),迭代执行一趟排序,直到数据全部有序。内循环的步长为正数,表示从前往后冒泡,负数表示从后往前冒泡,步长大于1,表示对局部数据进行排序。外循环次数决定排序的趟数,n个数据最多需要n-1趟排序,实现全部数据有序。
　　冒泡排序可以用双重循环来实现,其算法复杂度为O(n2),外循环决定排序的趟数,内循环实现第i趟排序的方向和区间,比较语句实现了升降序的方式。内循环的初值和终值决定待排序(无序)区间的两个端点,range函数的3个参数分别表示开始start、结束stop和步长step。冒泡排序的特征是开始位置是固定的,相邻两个对象进行比较和交换。从前往后冒泡,步长step为1,实现后面数据先有序,随着排序趟数i的增加,结束位置在不断地减少,因此参数stop中包含-i这一因子。从后往前冒泡,步长step为-1,实现前面数据先有序,随着排序趟数i的增加,结束位置在不断地增大,因此参数stop中包含+i这一因子。
1.有一个数组采用冒泡排序,第1遍排序后的结果为:3,18,5,35,8,9,11,13,32,那么该数组的原始顺序不可能是(　　)
A.18,5,35,8,9,11,3,13,32
B.3,18,5,35,13,11,32,8,9
C.18,5,35,3,8,9,11,13,32
D.18,5,35,8,9,11,13,32,3
答案　B
解析　本题主要考查冒泡排序。第1趟排序后最大值在中间,最小值在最左侧,是对原始数据进行了从后往前的升序排列,按此排序方式,只有B项符合要求。
2.采用冒泡排序算法,对某数组数据进行排序,经过一轮后的结果是“2,3,9,5,6,7”,那么下列说法不正确的是(　　)
A.这轮排序,有可能没发生数据交换
B.这轮排序,有可能只发生了1次数据交换
C.排序结束后,数据是升序的
D.完成全部排序后,数据交换的次数和冒泡的方向无关
答案　A
解析　本题考查冒泡排序。经过一轮后最小数在最前面,可知,该冒泡排序是从后往前冒泡,升序。A选项原始数据最小数2不在最前面,一定会发生交换。若原始数据就是一趟排序结果,9在中间,无论是从后往前,还是从前往后,都要发生数据交换。B选项若原始数据如果为“2,3,5,9,6,7”,那么就发生了一次交换。C选项从一趟结果来看,是升序排列。D选项数据的交换取决于逆序对的个数,与排序方向无关。
3.采用冒泡排序算法对数据序列“2,3,4,5,1,0”完成升序排序,则需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.18次
答案　A
解析　本题考查教材上的冒泡排序算法基本原理。第一趟交换 5 次,序列为“0,2,3,4,5,1,”。第二趟交换4次,序列为“0,1,2,3,4,5”。至此数据已经有序,无需交换。共交换9次。
4.列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for i in range(n-1):
　for j in range(n-1,i+1,-1):
　　 if s[j]>s[j-1]:
　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[7]的降序排列
B.s[0]到s[7]的升序排列
C.s[1]到s[7]的降序排列
D.s[1]到s[7]的升序排列
答案　C
解析　本题考查冒泡排序的算法思想。一共排了n-1趟,从内循环来看,实现从后往前冒泡排序。当i为0时,终值能取到2。第1次为s[7]和s[6]比较,最后一次为s[2]和s[1]比较,因此实现s[1]到s[7]的降序排列。
5.小明编写程序实现数据排序功能,部分程序如下:
n = len(d)
for i in range(1, n):
　for j in range(n - i - 1, -1, -1):
　　 if d[j]> d [j+ 1]:
　　　　d[j],d[j +1]=d[j + 1], d[j]
print(d)
此程序存在问题,不适合作为测试数据的是(　　)
A.d=[9,6,5,8] B.d=[9,8,6,5]
C.d=[8,9,5,6] D.d=[6,5,9,8]
答案　D
解析　实现从后往前冒泡升序排列,前面的数据先有序,但右端没有固定,每趟都在缩减,因此有些数据是排不到的。AB选项排序后均为5,6,9,8,无序,可以检测。C选项排序后为5,8,9,6,无序,可以检测。D选项排序为升序,与正确算法结果相同,无法检测。
6.某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.若s的初始值已有序,则该算法的时间复杂度为 O(1)
D.每一遍加工中,最小的元素“上浮”
答案　D
解析　本题考查排序算法。当条件s[j]1.对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后的数据序列为:31,24,23,15,20,10,则该数据序列的原始顺序不可能的是(　　)
A.24,23,15,31,10,20
B.24,23,15,20,31,10
C.24,31,23,15,10,20
D.23,24,15,20,31,10
答案　 D
解析　A、B选项符合从后往前比较,将最小数交换到最前面,C选项符合从前往后比较,将最大的数交换到最右边。而D选项不管从哪个方向进行依次比较,都不符合。
2.采用冒泡排序算法对数据序列“8,7,2,3,9,6,5”完成升序排序,排序2趟后,正确的顺序是(　　)
A.2,3,8,7,5,6,9 B.2,3,8,7,9,6,5
C.2,3,5,6,7,8,9 D.2,3,7,5,6,8,9
答案　A
解析　本题考查冒泡排序的算法思想。从后往前依次比较相邻两个位置数据的大小,并把较小数据换到前一位置。排序结果为2,3,8,7,5,6,9。从前往后冒泡的结果为2,3,7,6,5,8,9。
3.采用冒泡排序算法对数据序列“4,7,3,2,8”完成降序排序,则需交换的次数为(　　)
A.5 B.6
C.8 D.10
答案　A
解析　本题考查冒泡排序。对数据序列“4,7,3,2,8”进行冒泡,注意默认冒泡为从后往前冒。第一趟:“8,4,7,3,2”,交换4次,第二趟:“8,7,4,3,2”,交换1次。完成排序,共5次。
4.执行下列Python程序段后,c[1]的值是(　　)
a=[12,5,24,6,9,18]
n=len(a);c=[0]*n
for i in range(1,n):
　for j in range(n-1,i-1,-1):
　　 if a[j]>a[j-1]:
　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　c[i]+=1
A.1 B.2
C.3 D.4
答案　D
解析　外循环控制排序趟数,因此c[i]表示第i趟交换的次数。第1趟元素18与9和6交换,元素24与5和12交换。
5.有如下Python程序:
a=[1,5,2,9,6,7]
n=len(a)
for i in range(n∥2):
　for j in range(n-1, i, -1):
　　 if a[j]>a[j-1]:
　　　　a[j],a[j-1]=a[j-1], a[j]
执行该程序段后,a的值是(　　)
A.[9,7,6,1,5,2] B.[9,7,6,5,2,1]
C.[1,2,5,6,7,9] D.[9,6,7,5,2,1]
答案　A
解析　从后往前冒泡,排了3趟。
6.有如下Python程序段:
s=[2,3,8,7,5]
for i in range(len(s)-1):
　 for j in range(len(s)-1,i,-1):
　　 if s[j]　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.6
C.8 D.10
答案　A
解析　加框处语句表示交换次数,从条件s[j]7.有以下Python程序段:
n=6
s=[5,9,8,6,7,1]
for i in range(3):
　for j in range(　　　　):
　　 if s[j]　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后,数据s的值为[5,6,8,9,7,1],则划线处的代码是(　　)
A.n-2,i,-1 B.1,n-i-1
C.1, n-i-2 D.n-1,i,-1
答案　C
解析　本题考查冒泡排序。该算法实现前4个数据的升序排列,因此排序的区间为[0,4],若要从后往前排序,第1项为n-3,结束位置为i+1。若要从前往后排序,则j的初值为1,当i为0时,最后的索引为n-3,因此j的终值为n-i-3,但终值必须为n-i-2才可以取到n-i-3。
8.对一组数进行错位排序,即从前往后依次是最小的,最大的,第二小的,第二大的……以此类推。如“77,52,32,82,43,21,90,28,46” 经过排序后,结果为“21,90,28,82,32,77,43,52,46”。实现该功能的Python程序段如下:
#随机生成n个2位的正整数,存储于a列表,代码略
tmp = 1
for i in range(n - 1):
　for j in range(n - 1, ①　　　　, -1):
　　 if ②　　　　:
　　　　a[j],a[j-1]=a[j-1],a[j]
　tmp = -tmp
则划线处应填入的代码为(　　)
A.①i+1　②tmp*(a[j]-a[j-1])<0
B.①i　②tmp*(a[j]-a[j-1])<0
C.①i　②tmp*(a[j]-a[j-1])>0
D.①i+1　②tmp*(a[j]-a[j-1])>0
答案　B
解析　实现从后往前冒泡排序,前面的数据先有序,第1趟排序时,i的值为0,有序的索引位置是0,比较对象是a[j]和a[j-1],即a[1]和a[0],j取值为1,但在rangk函数中,还需加是步长-1,因此排除选项A和D。第1趟是降序,此时tmp的值为1,因此当a[j]-a[j-1]小于0时,需交换。
9.有以下Python程序段:
s=[5,9,8,6,7,1,4,2]
n=len(s)
for i in range(1,n∥2):
　 for j in range(　　　　 ):
　　 if s[j]　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后实现数据部分有序,结果s的值为[5,9,1,6,7,8,4,2],则划线处的代码是(　　)
A.n-3,i+1,-1 B.i+1,n-i-1
C.n-1,i-1,-1 D.2,n-i+1
答案　A
解析　只需对a[2]到a[5]范围进行排序,排除选项C。range的第1个参数为定值,因此排除选项B。若从前往后冒泡,被比较的是a[j]与a[j-1],当i的值为1时,n-i+1的值为8,导致后面的数据也会参加排序,排除选项D。若从后往前冒泡,每次总是从n-3开始,第1趟最后1次比较的对象为s[3]和s[2],即j的值为3,因此第2个参数为i+1。
10.数组 L长度为n,要实现数组元素 L[a]至 L[b]升序排列(0≤afor i in range(0, b-a):
　 for j in range(b-1, a-1,-1):
　　 if L[j] < L[j - 1]:
　　　　L[j], L[j - 1] = L[j - 1], L[j]
加框处代码在测试程序时发现有误,可修改为(　　)
A.range(a,b-1) B.range(b,a-i,-1)
C.range(b,a+i,-1) D.range(a-i+1,b)
答案　C
解析　若从前往后冒泡,初始位置a固定,第i趟实现b-i位置有序,j的值为b-i-1,在range的终值为b-i。步长为1。从后往前冒泡,初始位置b固定。第i趟实现a+i位置有序,j的值为a+i+1,在range的终值为a+i。步长为-1。
11.下列代码采用冒泡排序对a列表中的n个数据升序排序,则①②两处不可用的选项是(　　)
for i in range(①　　　　):
　 for j in range(②　　　　):
　　 if a[j] 　　　　a[i],a[j-1] =a[j- 1],a[j]
A.①1,n　②n-1,i-1,-1
B.①n, 1,-1　②1,i-1
C.①1,n　②1,n-i+1
D.①0, n-1　②n-1,i-1
答案　B
解析　本题考查冒泡排序的算法思想。当i=n时,j in range(1,n-1),当j为最后一个值n-2时(range右边为开区间,n-1取不到),a[n-2]与a[n-3]比较大小,缺少a[n-1]与a[n-2]比较大小,不能完成所有n个数据的升序排序。(共56张PPT)
选修一　数据与数据结构
课时28　冒泡排序算法
知识点 学业水平等级
1.从相邻数据比较和交换的本质理解冒泡排序的算法思想。 4
2.通过对内、外循环和比较语句的功能,用程序代码实现冒泡排序。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　冒泡排序算法是迭代算法思想的重要体现,排序的趟数决定了迭代的次数,因此明确迭代的对象以及迭代后的结果是本节课的重要内容。在2023年6月卷中,考查了排序(迭代)的范围以及排序的过程,要求学生掌握排序后的结果。
(2023年6月浙江选考)列表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]的升序排列
解析　本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1,5],条件s[j]>s[j-1]表示当后一个数大于前一个数时要发生交换,实现降序排列。参加排序元素仅s[0]~s[5]。
A
知识梳理
2
1.　　　　(sorting)是使系列中的元素按照某个字段的值递增(或递减)的次序重新排列的操作。在排序的过程中,元素的值保持不变,但其在系列中的顺序可能会改变。
2.待排序的数据存储方式一般有　　　　和链表两种方式,利用数组存储数据,在排序时需要对数据本身进行物理重排,可能需要移动数据的位置,而利用链表存储数据,只需要修改指针即可。
3.常见的排序算法有　　　　排序、选择排序、插入排序、快速排序、堆排序、归并排序、桶排序等。在选择排序的算法时,可以根据待排序数据自身的特点来选择相应的算法。
排序
数组
冒泡
4.冒泡排序(Bubble_Sort)是在一系列数据中对　　　　两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
5.冒泡排序算法把待排序的n个元素的数组看成垂直堆放的一列数据,对相邻两个数据进行比较,将较　　　　的数据换到上面的一个元素中(升序)。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。当第一遍加工完成时,最小的数据已经“上浮”到第一个元素的位置(升序)。然后对余下的n-1个元素重复上述处理过程,直到最后进行余下两个数据的比较和交换。
相邻
小
6.对于n个元素的数组,共需要　　　　遍加工,第一遍加工的比较次数为　　　次,第二遍加工的比较次数为n-2次,以此类推,最后一遍加工的比较只需　　　　次。所以用冒泡排序算法进行排序时,共需比较n(n-1)/2(次)。其时间复杂度为　　　　。
n-1
n-1
1
O(n2)
课堂突破
3
【典例1】 采用冒泡排序算法对某数据序列进行排序,第一轮排序后的结果是“2,8,6,3,5,7,9”,则第二轮排序需要交换的次数为(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
答案　A
思维点拨
明考向 本题考查冒泡排序算法的算法思想
精点拨 由第一轮数据“2,8,6,3,5,7,9”可知,采用冒泡排序对数据进行升序排序,但有两种可能,一种是从后往前的冒泡升序,则第二轮排序后的数据为“2,3,8,6,5,7,9”,交换2次,另一种是从前往后的冒泡升序,则第二轮排序后的数据为“2,6,3,5,7,8,9”,交换4次
【变式1】 采用冒泡排序算法对数据序列“22,35,43,56,19,8”完成升序排序,需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.21次
解析　本题考查冒泡排序算法的算法思想。找出各个逆序对。比22小且在右侧的数有19和8共2个。同理比35、43和56小且在右侧的数各有2个。比19小的数有1个。一共有9对逆序对。
A
【典例2】 列表s包含8个互不相等的元素,即s[0],s[1],s[2],...s[7],有如下Python程序段:
n=8
for i in range(1,5):
　for j in range(n-2,i,-1):
　　 if s[j]　　　　s[j],s[j+1]=s[j+1],s[j]
该程序段实现的是(　　)
A.s[0]到 s[3]的升序排列 B.s[4]到 s[7]的升序排列
C.s[2]到 s[5]的降序排列 D.s[1]到 s[4]的降序排列
答案　C
思维点拨
明考向 本题考查冒泡排序算法实现
精点拨 从后往前冒泡,前面的数据先有序,有序区间的左端点是i+1,比较对象是s[j]【变式2】 互不相等的10个列表元素s[0]、s[1]、s[2]……s[9],有如下Python程序段:
n=10
for i in range(5):
　for j in range(1,n-i):
　　 if s[j]>s[j-1]:
　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到 s[5]的降序排列 B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列 D.s[5]到 s[9]的升序排列
解析　本题考查冒泡排序算法思想。分析冒泡排序内循环的代码,是从左(前)向右(后)冒泡、降序。外循环只进行了5次,所以只有最后5个数(s[5]到 s[9])是有序的。
C
【典例3】 n名考生的考号和成绩保存在数组cj中,如[["230101",98],
["230109",97]……],现要按成绩从高到低录取k(kfor i in range(n-1):
　for j in range(①　　　　):
　　 if cj[j][1]>cj[j-1][1]:
　　　　cj[j],cj[j-1]=cj[j-1],cj[j]
　if ②　　　　 and cj[i][1]!=cj[i-1][1]:
　　 break
print("录取考生的考号有:")
for j in range(③　　　　):
　print(cj[j][0],end=" ")
答案　①n-1,i,-1　②i>=k　③i
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 ①排序的方向和区间。成绩从高到低录取考生,需进行降序排列,实现前面的数据先有序,因此需从后往前冒泡。第i趟排序实现前面第i位置数据有序,因此第1次比较位置n-1和n-2,最后1次比较位置i和i+1,j的终值为i+1,步长为-1,但range是一个左闭右开的区间。②最后一名成绩相同者均可进入面试,因此结束排序的条件有两个,就是i的值大于等于k且他与前面的成绩不相等。③找到第1个不符合条件学生的索引为i,因此只需输出索引为0至i-1的学生考号
【变式3】 有如下Python程序段:
L=[21,12,13,17,16,15,20,28,11]
def shengxu(a,b):
　for i in range(0,b-a):
　　 for j in range(　　　　　 ):
　　　 if L[j]>L[j+1]:
　　　　　L[j],L[j+1]=L[j+1],L[j]
shengxu(3,7)
print(L)
若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为(　　)
A.i,b B.0,b- i
C.a,b-i D.b-1,a-i-1,-1
解析　本题考查冒泡排序的算法实现。外循环控制排序的次数,也与排序的区间位置有关。冒泡排序必须是一端固定,另一端随着排序的过程将不断地缩短。若从前往后冒泡,则排序的初值必须为a,第一趟排序的区间是最长的,此时i的值为0,最后位置为b,而j+1到过b时,j的值为b-1,若要取到b-1,则终值必须为b,结合i的值,终值为b-i。
C
　　排序往往先找出一列数中的最值,将这个最值交换到该列数的末端,把数列划分为有序区间和无序区间,把这个操作称为一趟排序。再对无序区间进行重复操作,不断地扩大有序区间,缩小无序区间,当无序区间中只有一个数据时,全部数据有序,结束排序。冒泡排序基本算法思想是每次总是从最左边或最右边的位置(开始位置是固定),迭代执行一趟排序,直到数据全部有序。内循环的步长为正数,表示从前往后冒泡,负数表示从后往前冒泡,步长大于1,表示对局部数据进行排序。外循环次数决定排序的趟数,n个数据最多需要n-1趟排序,实现全部数据有序。
　　冒泡排序可以用双重循环来实现,其算法复杂度为O(n2),外循环决定排序的趟数,内循环实现第i趟排序的方向和区间,比较语句实现了升降序的方式。内循环的初值和终值决定待排序(无序)区间的两个端点,range函数的3个参数分别表示开始start、结束stop和步长step。冒泡排序的特征是开始位置是固定的,相邻两个对象进行比较和交换。从前往后冒泡,步长step为1,实现后面数据先有序,随着排序趟数i的增加,结束位置在不断地减少,因此参数stop中包含-i这一因子。从后往前冒泡,步长step为-1,实现前面数据先有序,随着排序趟数i的增加,结束位置在不断地增大,因此参数stop中包含+i这一因子。
当堂检测
4
B
解析　本题主要考查冒泡排序。第1趟排序后最大值在中间,最小值在最左侧,是对原始数据进行了从后往前的升序排列,按此排序方式,只有B项符合要求。
A
解析　本题考查冒泡排序。经过一轮后最小数在最前面,可知,该冒泡排序是从后往前冒泡,升序。A选项原始数据最小数2不在最前面,一定会发生交换。若原始数据就是一趟排序结果,9在中间,无论是从后往前,还是从前往后,都要发生数据交换。B选项若原始数据如果为“2,3,5,9,6,7”,那么就发生了一次交换。C选项从一趟结果来看,是升序排列。D选项数据的交换取决于逆序对的个数,与排序方向无关。
3.采用冒泡排序算法对数据序列“2,3,4,5,1,0”完成升序排序,则需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.18次
A
解析　本题考查教材上的冒泡排序算法基本原理。第一趟交换 5 次,序列为“0,2,3,4,5,1,”。第二趟交换4次,序列为“0,1,2,3,4,5”。至此数据已经有序,无需交换。共交换9次。
4.列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for i in range(n-1):
　for j in range(n-1,i+1,-1):
　　 if s[j]>s[j-1]:
　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[7]的降序排列 B.s[0]到s[7]的升序排列
C.s[1]到s[7]的降序排列 D.s[1]到s[7]的升序排列
C
解析　本题考查冒泡排序的算法思想。一共排了n-1趟,从内循环来看,实现从后往前冒泡排序。当i为0时,终值能取到2。第1次为s[7]和s[6]比较,最后一次为s[2]和s[1]比较,因此实现s[1]到s[7]的降序排列。
5.小明编写程序实现数据排序功能,部分程序如下:
n = len(d)
for i in range(1, n):
　for j in range(n - i - 1, -1, -1):
　　 if d[j]> d [j+ 1]:
　　　　d[j],d[j +1]=d[j + 1], d[j]
print(d)
D
解析　实现从后往前冒泡升序排列,前面的数据先有序,但右端没有固定,每趟都在缩减,因此有些数据是排不到的。AB选项排序后均为5,6,9,8,无序,可以检测。C选项排序后为5,8,9,6,无序,可以检测。D选项排序为升序,与正确算法结果相同,无法检测。
6.某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.若s的初始值已有序,则该算法的时间复杂度为 O(1)
D.每一遍加工中,最小的元素“上浮”
D
解析　本题考查排序算法。当条件s[j]课时作业
5
D
解析　A、B选项符合从后往前比较,将最小数交换到最前面,C选项符合从前往后比较,将最大的数交换到最右边。而D选项不管从哪个方向进行依次比较,都不符合。
2.采用冒泡排序算法对数据序列“8,7,2,3,9,6,5”完成升序排序,排序2趟后,正确的顺序是(　　)
A.2,3,8,7,5,6,9 B.2,3,8,7,9,6,5
C.2,3,5,6,7,8,9 D.2,3,7,5,6,8,9
A
解析　本题考查冒泡排序的算法思想。从后往前依次比较相邻两个位置数据的大小,并把较小数据换到前一位置。排序结果为2,3,8,7,5,6,9。从前往后冒泡的结果为2,3,7,6,5,8,9。
3.采用冒泡排序算法对数据序列“4,7,3,2,8”完成降序排序,则需交换的次数为(　　)
A.5 B.6
C.8 D.10
A
解析　本题考查冒泡排序。对数据序列“4,7,3,2,8”进行冒泡,注意默认冒泡为从后往前冒。第一趟:“8,4,7,3,2”,交换4次,第二趟:“8,7,4,3,2”,交换1次。完成排序,共5次。
4.执行下列Python程序段后,c[1]的值是(　　)
a=[12,5,24,6,9,18]
n=len(a);c=[0]*n
for i in range(1,n):
　for j in range(n-1,i-1,-1):
　　 if a[j]>a[j-1]:
　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　c[i]+=1
A.1　　　　　　B.2　　　　　　C.3　　　　　　D.4
D
解析　外循环控制排序趟数,因此c[i]表示第i趟交换的次数。第1趟元素18与9和6交换,元素24与5和12交换。
5.有如下Python程序:
a=[1,5,2,9,6,7]
n=len(a)
for i in range(n∥2):
　for j in range(n-1, i, -1):
　　 if a[j]>a[j-1]:
　　　　a[j],a[j-1]=a[j-1], a[j]
执行该程序段后,a的值是(　　)
A.[9,7,6,1,5,2] B.[9,7,6,5,2,1]
C.[1,2,5,6,7,9] D.[9,6,7,5,2,1]
A
解析　从后往前冒泡,排了3趟。
A
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.6
C.8 D.10
解析　加框处语句表示交换次数,从条件s[j]7.有以下Python程序段:
n=6
s=[5,9,8,6,7,1]
for i in range(3):
　for j in range(　　　　):
　　 if s[j]　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后,数据s的值为[5,6,8,9,7,1],则划线处的代码是(　　)
A.n-2,i,-1 B.1,n-i-1
C.1, n-i-2 D.n-1,i,-1
C
解析　本题考查冒泡排序。该算法实现前4个数据的升序排列,因此排序的区间为[0,4],若要从后往前排序,第1项为n-3,结束位置为i+1。若要从前往后排序,则j的初值为1,当i为0时,最后的索引为n-3,因此j的终值为n-i-3,但终值必须为n-i-2才可以取到n-i-3。
8.对一组数进行错位排序,即从前往后依次是最小的,最大的,第二小的,第二大的……以此类推。如“77,52,32,82,43,21,90,28,46” 经过排序后,结果为“21,90,28,82,32,77,43,52,46”。实现该功能的Python程序段如下:
#随机生成n个2位的正整数,存储于a列表,代码略
tmp = 1
for i in range(n - 1):
　for j in range(n - 1, ①　　　　, -1):
　　 if ②　　　　:
　　　　a[j],a[j-1]=a[j-1],a[j]
　tmp = -tmp
则划线处应填入的代码为(　　)
A.①i+1　②tmp*(a[j]-a[j-1])<0
B.①i　②tmp*(a[j]-a[j-1])<0
C.①i　②tmp*(a[j]-a[j-1])>0
D.①i+1　②tmp*(a[j]-a[j-1])>0
B
解析　实现从后往前冒泡排序,前面的数据先有序,第1趟排序时,i的值为0,有序的索引位置是0,比较对象是a[j]和a[j-1],即a[1]和a[0],j取值为1,但在rangk函数中,还需加是步长-1,因此排除选项A和D。第1趟是降序,此时tmp的值为1,因此当a[j]-a[j-1]小于0时,需交换。
9.有以下Python程序段:
s=[5,9,8,6,7,1,4,2]
n=len(s)
for i in range(1,n∥2):
　 for j in range(　　　　 ):
　　 if s[j]　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后实现数据部分有序,结果s的值为[5,9,1,6,7,8,4,2],则划线处的代码是(　　)
A.n-3,i+1,-1 B.i+1,n-i-1
C.n-1,i-1,-1 D.2,n-i+1
A
解析　只需对a[2]到a[5]范围进行排序,排除选项C。range的第1个参数为定值,因此排除选项B。若从前往后冒泡,被比较的是a[j]与a[j-1],当i的值为1时,n-i+1的值为8,导致后面的数据也会参加排序,排除选项D。若从后往前冒泡,每次总是从n-3开始,第1趟最后1次比较的对象为s[3]和s[2],即j的值为3,因此第2个参数为i+1。
C
解析　若从前往后冒泡,初始位置a固定,第i趟实现b-i位置有序,j的值为b-i-1,在range的终值为b-i。步长为1。从后往前冒泡,初始位置b固定。第i趟实现a+i位置有序,j的值为a+i+1,在range的终值为a+i。步长为-1。
11.下列代码采用冒泡排序对a列表中的n个数据升序排序,则①②两处不可用的选项是(　　)
for i in range(①　　　　):
　 for j in range(②　　　　):
　　 if a[j] 　　　　a[i],a[j-1] =a[j- 1],a[j]
A.①1,n　②n-1,i-1,-1 B.①n, 1,-1　②1,i-1
C.①1,n　②1,n-i+1 D.①0, n-1　②n-1,i-1
B
解析　本题考查冒泡排序的算法思想。当i=n时,j in range(1,n-1),当j为最后一个值n-2时(range右边为开区间,n-1取不到),a[n-2]与a[n-3]比较大小,缺少a[n-1]与a[n-2]比较大小,不能完成所有n个数据的升序排序。

展开更多......

收起↑