资源简介

专题11　排序算法
学习目标　
1.了解冒泡排序本质是相邻两个数进行比较和交换，让较大的数“下沉(上冒)”，较小的数“上冒(下沉)”的一种排序技术；
2.写出每趟排序的结果，掌握每趟的比较次数、每趟的排序区间和每趟排序实现的功能；
3.列出排序序列中的逆序对，掌握总共需要的交换次数；
4.外循环实现排序的趟数，内循环决定排序的方向和区间，比较条件决定排序的方式；
5.根据外循环变量i，画出待排序区间，在待排序区间的两端写出4个比较的位置，从而确定内循环的初始和结束位置.
冒泡排序的特征是相邻两个对象进行比较和交换，可以从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。当某趟排序过程中没有发生数据交换，表示整个序列数据有序，可以提前结束排序。冒泡排序可以用双重循环来实现，其算法复杂度为O(n2)，外循环表示循环的趟数，内循环实现第i趟排序的方向和区间，比较语句实现了升降序的方式。
(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]的升序排列
重难点1　冒泡排序的算法思想
从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。排序往往先找出一列数中的最值，将这个最值交换到该列数的末端，把数列划分为有序区间和无序区间，把这个操作称为一趟排序。再对无序区间进行重复操作，不断地扩大有序区间，缩小无序区间，当无序区间中只有一个数据时，全部数据有序，结束排序。排序基本算法思想是迭代执行一趟排序，直到数据全部有序。内循环的步长为正数，表示从前往后冒泡，负数表示从后往前冒泡，步长大于1，表示对局部数据进行排序。外循环次数决定排序的趟数，n个数据最多需要n－1趟排序，实现全部数据有序。内循环的初值和终值决定待排序(无序)区间的两个端点。
例1 有如下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]　　　　
执行该程序段，加框处语句被执行的次数是(　　)
A.3 B.6 C.8 D.10
变式1 某 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.每一遍加工中，最小的元素“上浮”
例2 列表lst中共有n个整数，若下列程序段实现将数组元素lst[st]至lst[ed]升序排列，则划线处的代码为(　　)
for i in range(st，ed)：
　 for j in range(st，________)：
　 if lst[j]>lst[j＋1]：
　　　　 lst[j]，lst[j＋1]＝lst[j＋1]，lst[j]
A.n－i B.ed－i
C.ed＋st－i D.st＋ed
变式2 数组L长度为n，要实现数组元素L[a]至L[b]升序排列(0≤afor 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]
加框处代码在测试程序时发现有误，可修改为(　　)
A.range(a, b－1) B.range (b, a－i, －1)
C.range(b, a＋i，－1) D.range (a－i＋1, b)
重难点2　冒泡排序的变式
外循环次数决定排序的趟数，从前往后冒泡，则后面部分数据有序，从后往前冒泡，则前面部分数据有序。利用这一特性，可以筛选达到要求的数据，提前结束排序。排序对象若为a[j]和a[j＋2]，则实现奇偶位分组排序。比较语句的大于或小于号决定了升降序的方式。当排序的条件有两个或多个时，或者出现了多分支的选择结构，实现的多关键字排序。
例1 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＝″″)
变式1 有如下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]
例2 使用列表a 和列表b 分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i], 使用 Python 编程实现如下功能：将成绩数据“按总分降序排序、总分相同按学号升序排序”，代码如下。
n＝len(a)
for i in range(1，n)：
　 for j in range(0，n－i)：
　 iforand：
　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　 b[j]，b[j＋1]＝b[j＋1]，b[j]
上述程序段中方框处可选代码为：
①a[j]>a[j＋1]　②a[j]＝＝a[j＋1]
③a[j]⑤b[j]＝＝b[j＋1]　⑥b[j]>b[j＋1]，则(1)(2)(3)处代码依次为(　　)
A.③②④ B.①⑤⑥ C.③②⑥ D.①⑤④
变式2 数组a包含10个不同的元素，即 a[0]，a[1]，…a[9]，有如下Python 程序段：
n ＝ len(a)
for i in range(0, n, 2)：
　 for j in range(n － 2, i ＋ 1, －2):
　 if a[j] < a[j － 2]：
　　　 a[j], a[j － 2] ＝ a[j － 2], a[j]
该程序段实现的功能是(　　)
A.仅对偶位元素a[0]，a[2]，…a[8]升序排列
B.仅对奇位元素a[1]，a[3]，…a[9]升序排列
C.偶位元素 a[0]，a[2]，…a[8]升序，奇位元素降序排列
D.偶位元素 a[0]，a[2]，…a[8]降序，奇位元素升序排列
重难点3　冒泡排序的优化
在排序过程中，若某趟排序没有发生数据交换，意味着数据已经有序，可以提前结束排序。外循环表示排序的趟数，同时也可以表示数据有序的位置。若实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。如原始数据为6，7，8，6，6，5，4，3，2，1，第一趟排序最后一次发生交换是a[1]和a[2]，有序位置索引号为2，下趟排序中只要包含位置1即可。
例题 有实现冒泡排序的python 程序段：
a＝[4, 6, 3, 9, 1, 2]
n＝len(a)
i＝n－1
while i>＝1：
　　k＝0
　　for j in range(i)：
　 if a[j]　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　 k＝j
　　____________
则划线处的语句应为(　　)
A.i＝k－1 B.i＝k
C.i＝k＋1 D.i＝j
变式 有如下Python程序，程序运行后，变量c的值为：
d＝[1, 7, 5, 2, 3]
flag＝False；last＝i＝c＝0 ；n＝len(d)－1
while i　　flag＝True
　　c＋＝1
　　for j in range(n，i，－1):
　 if d[j]　　　　 d[j]，d[j－1]＝d[j－1]，d[j]
　　　　 flag＝False；last＝j
　　i＝last
A.2 B.3 C.4 D.5
重难点1　冒泡排序的算法思想
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
2.采用冒泡排序算法对数据序列“4，7，3，2，8”完成降序排序，则需交换的次数为(　　)
A.5 B.6 C.8 D.10
3.某排序算法的Python程序段如下：
'读取n个整数，依次存入a[1]到a[n]中，代码略
for i in range(1，n－1)：
　 for j in range(n，i＋1，－1) ：
　 if a[j]>a[j－1] ：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
执行上述程序段，下列说法正确的是(　　)
A.交换过位置的数据，可能会再回到其初始位置
B.执行完成后，数组元素 a[1]到 a[n]从小到大排列
C.若n为 6，整个排序过程总的比较次数是30
D.整个排序过程总的交换次数至少为1
4.如下 Python 程序段：
s＝list(″bcaabca″)
n＝len(s)
for i in range(1，n)：
　 for j in range(n－1，i－1，－1)：
　 if s[j]＝＝'a' and s[j－1]！＝'a'：
　　　　 s[j]，s[j－1]＝s[j－1]，s[j]
print(s)
执行该程序段后，输出的内容为(　　)
A.['b'，'c'，'b'，'c'，'a'，'a'，'a']
B.['b'，'b'，'c'，'c'，'a'，'a'，'a']
C.['a'，'a'，'a'，'b'，'c'，'b'，'c']
D.['a'，'a'，'a'，'b'，'b'，'c'，'c']
5.列表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]的降序排列
重难点2　冒泡排序的变式
1.有以下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
2.有如下Python程序段：
a＝[3，6，7，2，8，2]; b＝[5，3，7，7，7，4]
for i in range(len(a)－1)：
　 for j in range(0，len(a)－i－1)：
　 if a[j]>a[j＋1] or a[j]＝＝a[j＋1] and b[j]　　　　 a[j], a[j＋1]＝a[j＋1], a[j]
　　　　 b[j], b[j＋1]＝b[j＋1], b[j]
执行上述程序段后，a[1]与b[1]的值分别是(　　)
A.8，7 B.7，7 C.2，4 D.2，7
3.有如下 Python 程序段：
import random
a ＝ [34，17，19，13，10，6，26，21]
x ＝ (random.randint(1，4))*2
for i in range(8－x)：
　 for j in range(7，i，－1):
　 if a[j] >a[j－1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
print(a[0：4])
程序段执行后，输出的结果不可能是(　　)
A.[34, 26, 21, 19] B.[34, 26, 21, 17]
C.[34, 26, 17, 19] D.[34, 17, 19, 13]
4.有如下Python程序段：
a＝list(map(int，input().split()))　#将输入的数据转换成列表
n＝len(a)
for i in range(2)：
　 for j in range(n－1，i，－1 )：
　 if a[j] % 3 > a[j－1] % 3：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
以下运行结果不可能的是(　　)
A.[20，50，10，40，30，60]
B.[5，8，1，3，4，6]
C.[9，17，16，4，12，5]
D.[17，11，1，4，9，6]
重难点3　冒泡排序的优化
1.列表s中包含n个互不相等的元素，用Python编程实现如下功能： s[0]到 s[n－1]降序排序，当序列已经有序时结束排序，部分代码如下。
n＝len(s)
for i in range(1，n)：
　
　for j in range()：
　 if　：
　　　　s[j]，s[j－1]＝s[j－1]，s[j]
　　　　flag ＝ True
　if flag＝＝False:
　 break
上述程序段中方框可选代码为： ①flag＝True　②flag＝False　③1，n－i＋1　④1，n－i　⑤s[j]s[j－1]，则(1)(2)(3)处代码依次为(　　)
A.②④⑥ B.②③⑥ C.①④⑤ D.①③⑥
2.列表lst中共有n个整数，若下列程序段实现将数组元素lst[st]至lst[ed]升序排列，
while st！＝ed：
　　________________
　　for j in range(st，ed)：
　 if m[j]>m[j＋1]：
　　　　 m[j]，m[j＋1]＝m[j＋1]，m[j]
　　　　 last＝j
　　ed＝last
则划线处的代码为________________
重难点1　冒泡排序的算法思想
1.采用冒泡排序算法对数据序列“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
2.采用冒泡排序算法对数据序列“2，3，4，5，1，0”完成升序排序，则需要交换的次数为(　　)
A.9次 B.12次 C.15次 D.18次
3.下列代码采用冒泡排序对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
4.小明编写程序实现数据排序功能，部分程序如下：
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]
5.有如下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
6.列表中有n个互不相等的元素，即s[0]，s[1]，s[2]，……s[n－1]，有如下Python程序段：
for i in range(①________)：
　 for j in range(②________)：
　 if s[j]>s[j－1]：
　　　　s[j]，s[j－1]＝s[j－1]，s[j]
上述程序段中划线处可选代码为：
①0，n－1　②1，n－1　③1，n　④1，n－i－1　⑤1，n－i　⑥1，n－i＋1
为完成元素的排序，(1)(2)处代码依次为(　　)
A.①④ B.①⑥ C.②⑤ D.③⑥
7.互不相等的 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]的升序排列
8.列表a包含n个互不相等的元素，依次为a[0]到a[n－1]，有如下Python程序段：
n＝6
for i in range(n－1)：
　 for j in range(n－2，i，－1)：
　 if a[j]>a[j＋1]：
　　　　 a[j], a[j＋1]＝a[j＋1], a[j]
执行该程序段后，下列说法正确的是(　　)
A.实现a[0]到a[5]的升序排序
B.总共的比较次数是10
C.总共的交换次数大于等于1
D.交换过的数据不会回到初始位置
9.列表a中各元素 a[0]到 a[4]的值依次为 9, 2, 5, 1, 3，若分别执行如下两段程序，则数据交换次数分别是(　　)
程序1
for i in range(1, len(a)－1)： 　 for j in range(1, len(a)－i)： 　 if a[j－1]>a[j]： 　　　　 a[j], a[j－1]＝a[j－1]，a[j]
程序2
for i in range(len(a)－1，1，－1)： 　 for j in range(len(a)－1，len(a)－i，－1): 　 if a[j－1] > a[j]： 　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
A.1和3 B.5和5 C.5和3 D.7和7
10.有如下Python程序段：
a＝int(input(″输入参数a：″))
b＝int(input(″输入参数b：″))
c＝int(input(″输入参数c：″))
for i in range(a，b，c)：
　 if f[i]　 f[i]，f[i＋1]＝f[i＋1]，f[i]
print(f)
执行该程序段后，若数组f中元素值依次为“7，4，6，5，3，2”，则数组f中元素初始值不可能是(　　)
A.7，2，4，6，5，3 B.4，7，5，6，3，2
C.7，4，5，6，2，3 D.4，6，7，2，3，5
重难点2　冒泡排序的变式
1.列表a中存储了8个元素，即a[0]，a[1]，…，a[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
　　　for j in range(n－1，i，－1)：
　if a[j]　　　　a[j－1]，a[j]＝a[j]，a[j－1]
该程序段实现的是(　　)
A.a[0]到a[7]升序排序
B.a[4]到a[7]升序排序
C.a[0]到a[7]的数据对4取余之后升序排序
D.a[0]到a[3]、a[4]到a[7]分别升序排序
2.有如下 Python 程序段：
m ＝ 3
lst ＝ [7，3，4，3，1，6，3]
for i in range(len(lst)－1)：
　 for j in range(len(lst)－1，i，－1):
　 if lst[j]　　　　 lst[j]，lst[j－1] ＝ lst[j－1], lst[j]
　
　break
执行该程序段，加框处语句被执行的次数是(　　)
A.3 B.4 C.5 D.6
3.某 Python程序如下：
a＝[3，8，6，2，3]
for i in range(len(a)－1，－1，－1)：
　 if a[i]%2＝＝0：
　 for j in range(i)：
　　　　 if a[j]>a[j＋1]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
程序运行后，输出的结果是(　　)
A.[2，6，8，3，3] B.[3，3，2，6，8]
C.[2，3，6，8，3] D.[2，3，3，6，8]
4.数组a包含10个互不相同的元素，即a[0]，a[1]，…，a[9]，其中a[0]，a[2]，…，a[8]称为奇数位元素，a[1]，a[3]，…，a[9]称为偶数位元素。有如下Python程序段：
n＝len(a)
for i in range(n∥2－1)：
　 for j in range(n－2，2*i，－2)：
　 if a[j]　　　　 a[j]，a[j－2]＝a[j－2]，a[j]
该程序段实现的功能是(　　)
A.仅对奇数位元素升序排列
B.仅对偶数位元素升序排列
C.奇数位元素升序，偶数位元素降序排列
D.奇数位元素降序，偶数位元素升序排列
5.有如下Python程序段：
from random import randint
n＝8
L＝[randint(10, 99) for i in range(n)]
for i in range(n－1)：
　 for j in range(i＋2，len(L)，2)：
　 if i%2＝＝1 and L[i]>L[j] or i%2＝＝0 and L[i]　　　　 L[i]，L[j]＝L[j]，L[i]
执行以上程序段，数组L的值不可能的是(　　)
A.[93，15，60，62，40，65，16，90]
B.[80，20，79，41，19，88，18，99]
C.[50，84，44，39，41，50，19，11]
D.[96，11，69，16，29，46，28，80]
6.有如下Python程序段：
s＝″ccbbac″
a＝[i for i in range(6)]
for i in range(5)：
　 for j in range( 5－i)：
　 if s[a[j]]>s[a[j＋1]]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
运行该程序段输出的结果为(　　)
A.[4，3，2，5，1，0] B.[4，5，3，2，1，0]
C.[4，2，3，0，1，5] D.[4，3，2，5，0，1]
7.小明对某校立定跳远测试成绩进行排序，要求女生在前，男生在后，同性别按成绩降序排序。实现功能的Python程序如下：
a＝[[″俞凯睿″，235，'男']，[″张佳妮″，210，'女']，[″王静怡″，220，'女']，[″顾筱杨″，260，'男']，[″李臣武″，250，'男']，[″陈丹祺″，230，'女']，[″李鸿慧″，240，'女']]
n＝len(a)
for i in range(n－1)：
　 for j in range(①________)：
　 if int(a[j][1]) > int(a[j－1][1]) and a[j][2] ＝＝ a[j－1][2]：
　 a[j]，a[j－1] ＝ a[j－1]，a[j]
　 elif　②________ ：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
为完成元素的排序，①②处代码依次为(　　)
A.①1，n－i－1
②a[j][2]＝＝″女″ and a[j－1][2]＝＝″男″
B.①n－1，i，－1
②a[j][2]＝＝″男″ and a[j－1][2]＝＝″女″
C.①1，n－i
②a[j][2]＝＝″女″ and a[j－1][2]＝＝″男″
D.①n－1，i＋1，－1
②a[j][2]＝＝″男″ and a[j－1][2]＝＝″女″
8.数组a中存储着全校学生的学号和BMI信息，格式为[['0101'，19.2]，['0102'，18.5]，['0103'，20.1]，...]。 其中每条数据的第一项为学号，第二项为BMI值。数组a已经按学号升序排序，现要求按照BMI值进行降序排序，BMI相同情况下仍然按照学号保持升序。则下列程序段可以实现该功能的是(　　)
A.for i in range(1，n)：
　　 for j in range(n－i)：
　 if a[j＋1] > a[j]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
B.for i in range(1，n)：
　　 for j in range(n－i)：
　 if a[j][1] > a[j＋1][1]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
C.for i in range(1, n)：
　　 for j in range(n－1, i－1, －1)：
　 if a[j][1] <＝ a[j－1][1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
D.for i in range(1, n)：
　　 for j in range(n－1, i－1, －1)：
　 if a[j][1] > a[j－1][1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
9.小明编写 Python程序对本校跳高测试成绩进行排序，规则如下：按照性别分别对成绩进行降序排序并输出名次(女生排前，男生排后，同分同名次)，计算结果如图所示
(1)程序中加框处代码有错，请改正。
(2)请在划线处填入合适的代码。
#把文件中的原始数据导入到数组a中，其中a[0][0]存储姓名，a[0][1]存储跳高成绩，a[0][2]存储性别，a[1][0]到a[1][2]存储第一位学生的相关信息，以此类推。代码略
for i in range(1，①________)：
　　　for j in range(1，len(a)－i)：
　if int(a[j][1])　　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
elif
　　　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
a[1][3]＝1
for i in range(2，len(a)):
　 if a[i][1]！＝a[i－1][1]：
a[i][3]＝i
　 else：
②________
t＝0
for i in range(1，len(a)):
　 if a[i][2]＝＝″女″：
③________
　 else：
a[i][3]＝a[i][3]－t
#输出数据 a 到文件中，代码略
重难点3　冒泡排序的优化
1.有如下Python程序段：
d＝[12，8，6，3，8，10]
i＝0；q＝0；flag＝False
while i　 flag＝True
　　for j in range(len(d)－1，q，－1):
　　 ：
　　　d[j]，d[j－1]＝d[j－1]，d[j]
　　　 q＝j
　　　 flag＝False
　　i＝i＋1
程序运行后，加框处语句执行次数为(　　)
A.15 B.12 C.9 D.8
2.有如下Python程序段：
d＝[11，9，23，4，8，10, 9，7]
n＝len(d)
p＝q＝0；cnt＝0
for i in range(1, n)：
　 cnt＝cnt＋1
　 for j in range(n－1，p，－1)：
　 if d[j]>d[j－1]：
　　　 d[j], d[j－1]＝d[j－1], d[j]
　　　 p＝j
　 if q＝＝p：
　 break
　 q＝p
print(cnt)
运行该程序段后，变量cnt 的值为(　　)
A.8 B.7 C.6 D.5
3.有如下 Python 程序段：
a＝[19，17，6，9，8]
n＝len(a)
f＝True；i＝4；k＝0
while i>0 and f：
　 f＝False
　　for j in range(i):
　 if a[j]　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 k＝k＋1；f＝True
　　i＝i－1
该程序段执行后，下列说法正确的是(　　)
A.数组a各元素的值是：6 8 9 17 19
B.变量k的值为 3
C.数组元素6在此过程中共交换了3次
D.变量i的值为 2
专题11　排序算法
学习目标　
1.了解冒泡排序本质是相邻两个数进行比较和交换，让较大的数“下沉(上冒)”，较小的数“上冒(下沉)”的一种排序技术；
2.写出每趟排序的结果，掌握每趟的比较次数、每趟的排序区间和每趟排序实现的功能；
3.列出排序序列中的逆序对，掌握总共需要的交换次数；
4.外循环实现排序的趟数，内循环决定排序的方向和区间，比较条件决定排序的方式；
5.根据外循环变量i，画出待排序区间，在待排序区间的两端写出4个比较的位置，从而确定内循环的初始和结束位置.
冒泡排序的特征是相邻两个对象进行比较和交换，可以从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。当某趟排序过程中没有发生数据交换，表示整个序列数据有序，可以提前结束排序。冒泡排序可以用双重循环来实现，其算法复杂度为O(n2)，外循环表示循环的趟数，内循环实现第i趟排序的方向和区间，比较语句实现了升降序的方式。
(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　冒泡排序的算法思想
从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。排序往往先找出一列数中的最值，将这个最值交换到该列数的末端，把数列划分为有序区间和无序区间，把这个操作称为一趟排序。再对无序区间进行重复操作，不断地扩大有序区间，缩小无序区间，当无序区间中只有一个数据时，全部数据有序，结束排序。排序基本算法思想是迭代执行一趟排序，直到数据全部有序。内循环的步长为正数，表示从前往后冒泡，负数表示从后往前冒泡，步长大于1，表示对局部数据进行排序。外循环次数决定排序的趟数，n个数据最多需要n－1趟排序，实现全部数据有序。内循环的初值和终值决定待排序(无序)区间的两个端点。
例1 有如下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]　　　　
执行该程序段，加框处语句被执行的次数是(　　)
A.3 B.6 C.8 D.10
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 加框处语句表示交换次数，从条件s[j]答案　A
变式1 某 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]例2 列表lst中共有n个整数，若下列程序段实现将数组元素lst[st]至lst[ed]升序排列，则划线处的代码为(　　)
for i in range(st，ed)：
　 for j in range(st，________)：
　 if lst[j]>lst[j＋1]：
　　　　 lst[j]，lst[j＋1]＝lst[j＋1]，lst[j]
A.n－i B.ed－i
C.ed＋st－i D.st＋ed
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 从前往后冒泡排序，后面的数据先有序，每趟待排序区右端点将则缩小。第一趟排序时，变量i的值为st，有序的索引位置为ed，若j要取到ed－1，则终值须为ed＋st－i－1，由于range是左闭右开的区间，因此终值为ed＋st－i
答案　C
变式2 数组L长度为n，要实现数组元素L[a]至L[b]升序排列(0≤afor 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]
加框处代码在测试程序时发现有误，可修改为(　　)
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。
重难点2　冒泡排序的变式
外循环次数决定排序的趟数，从前往后冒泡，则后面部分数据有序，从后往前冒泡，则前面部分数据有序。利用这一特性，可以筛选达到要求的数据，提前结束排序。排序对象若为a[j]和a[j＋2]，则实现奇偶位分组排序。比较语句的大于或小于号决定了升降序的方式。当排序的条件有两个或多个时，或者出现了多分支的选择结构，实现的多关键字排序。
例1 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
变式1 有如下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趟，因此把最大的3个数据推到最左边。
例2 使用列表a 和列表b 分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i], 使用 Python 编程实现如下功能：将成绩数据“按总分降序排序、总分相同按学号升序排序”，代码如下。
n＝len(a)
for i in range(1，n)：
　 for j in range(0，n－i)：
　 iforand：
　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　 b[j]，b[j＋1]＝b[j＋1]，b[j]
上述程序段中方框处可选代码为：
①a[j]>a[j＋1]　②a[j]＝＝a[j＋1]
③a[j]⑤b[j]＝＝b[j＋1]　⑥b[j]>b[j＋1]，则(1)(2)(3)处代码依次为(　　)
A.③②④ B.①⑤⑥ C.③②⑥ D.①⑤④
思维点拨
明考向 本题考查双关键字冒泡排序
精点拨 程序实现从前向后冒泡，第一关键字③：第j个比j＋1个成绩小则交换。第二关键字②⑥：第j个和第j＋1个成绩相同且第j个考号比第j＋1个大则交换
答案　C
变式2 数组a包含10个不同的元素，即 a[0]，a[1]，…a[9]，有如下Python 程序段：
n ＝ len(a)
for i in range(0, n, 2)：
　 for j in range(n － 2, i ＋ 1, －2):
　 if a[j] < a[j － 2]：
　　　 a[j], a[j － 2] ＝ a[j － 2], a[j]
该程序段实现的功能是(　　)
A.仅对偶位元素a[0]，a[2]，…a[8]升序排列
B.仅对奇位元素a[1]，a[3]，…a[9]升序排列
C.偶位元素 a[0]，a[2]，…a[8]升序，奇位元素降序排列
D.偶位元素 a[0]，a[2]，…a[8]降序，奇位元素升序排列
答案　A
解析　本题考查冒泡排序的算法思想。内循环j，初值为n－2＝8，步长为－2，因此j的值为8至2的偶数。比较对象也是这些位置中的数，因此仅实现这些数的升序排列。
重难点3　冒泡排序的优化
在排序过程中，若某趟排序没有发生数据交换，意味着数据已经有序，可以提前结束排序。外循环表示排序的趟数，同时也可以表示数据有序的位置。若实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。如原始数据为6，7，8，6，6，5，4，3，2，1，第一趟排序最后一次发生交换是a[1]和a[2]，有序位置索引号为2，下趟排序中只要包含位置1即可。
例题 有实现冒泡排序的python 程序段：
a＝[4, 6, 3, 9, 1, 2]
n＝len(a)
i＝n－1
while i>＝1：
　　k＝0
　　for j in range(i)：
　 if a[j]　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　 k＝j
　　____________
则划线处的语句应为(　　)
A.i＝k－1 B.i＝k
C.i＝k＋1 D.i＝j
思维点拨
明考向 本题考查冒泡排序的算法思想及算法的优化
精点拨 从内循环来看，实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。第1趟结果为[6，4，9，3，2，1]，下趟排序终点为4；第2趟结果为[6，9，4，3，2，1]，下趟排序终点为1；第3趟结果为[9，6，4，3，2，1]，下趟排序终点为0
答案　B
变式 有如下Python程序，程序运行后，变量c的值为：
d＝[1, 7, 5, 2, 3]
flag＝False；last＝i＝c＝0 ；n＝len(d)－1
while i　　flag＝True
　　c＋＝1
　　for j in range(n，i，－1):
　 if d[j]　　　　 d[j]，d[j－1]＝d[j－1]，d[j]
　　　　 flag＝False；last＝j
　　i＝last
A.2 B.3 C.4 D.5
答案　B
解析　本题考查冒泡排序的算法实现及算法的优化。变量c统计冒泡排序的排序趟数。程序实现从后向前升序排列，d[j]和d[j－1]比较，d[j－1]先有序，因此j是无序区间的开始位置。flag变量的作用是本趟排序数据是否有交换，若没有交换，直接退出循环，否则用变量last记录无序区间的开始位置。
重难点1　冒泡排序的算法思想
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.采用冒泡排序算法对数据序列“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次。
3.某排序算法的Python程序段如下：
'读取n个整数，依次存入a[1]到a[n]中，代码略
for i in range(1，n－1)：
　 for j in range(n，i＋1，－1) ：
　 if a[j]>a[j－1] ：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
执行上述程序段，下列说法正确的是(　　)
A.交换过位置的数据，可能会再回到其初始位置
B.执行完成后，数组元素 a[1]到 a[n]从小到大排列
C.若n为 6，整个排序过程总的比较次数是30
D.整个排序过程总的交换次数至少为1
答案　A
解析　考查冒泡排序算法思想。算法实现从左往右降序排列。A选项例如某个数后面有2个数，且一个数大他小，一个数比他大，当大的数往前交换后，第2次比他小的数又换回来了。总的比较次数为n*(n－1)/2＝15。D选项如果原数据已经有序了，不会发生交换。
4.如下 Python 程序段：
s＝list(″bcaabca″)
n＝len(s)
for i in range(1，n)：
　 for j in range(n－1，i－1，－1)：
　 if s[j]＝＝'a' and s[j－1]！＝'a'：
　　　　 s[j]，s[j－1]＝s[j－1]，s[j]
print(s)
执行该程序段后，输出的内容为(　　)
A.['b'，'c'，'b'，'c'，'a'，'a'，'a']
B.['b'，'b'，'c'，'c'，'a'，'a'，'a']
C.['a'，'a'，'a'，'b'，'c'，'b'，'c']
D.['a'，'a'，'a'，'b'，'b'，'c'，'c']
答案　C
解析　本题考查冒泡排序的变形。根据 if 条件s[j]＝＝'a' and s[j－1]！＝'a'可以看出，取字符串 s 中字符时，若当前字符 s[j]为'a'但 s[j－1]不为'a'，交换 s[j－1]与 s[j]的位置。因此，该程序段的功能为将字符'a'前移，其他字符保持原位置不变，交换后的结果为C.['a', 'a', 'a', 'b', 'c', 'b', 'c']。
5.列表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　冒泡排序的变式
1.有以下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。
2.有如下Python程序段：
a＝[3，6，7，2，8，2]; b＝[5，3，7，7，7，4]
for i in range(len(a)－1)：
　 for j in range(0，len(a)－i－1)：
　 if a[j]>a[j＋1] or a[j]＝＝a[j＋1] and b[j]　　　　 a[j], a[j＋1]＝a[j＋1], a[j]
　　　　 b[j], b[j＋1]＝b[j＋1], b[j]
执行上述程序段后，a[1]与b[1]的值分别是(　　)
A.8，7 B.7，7 C.2，4 D.2，7
答案　C
解析　本题考查双关键字排序。数组a中数据升序，当a数组中值相等时，以b数组对应的值为依据，即b数组中数据降序。 数组a中最小有2个2，b数组分别对应为7和4，b中7排在前面。
3.有如下 Python 程序段：
import random
a ＝ [34，17，19，13，10，6，26，21]
x ＝ (random.randint(1，4))*2
for i in range(8－x)：
　 for j in range(7，i，－1):
　 if a[j] >a[j－1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
print(a[0：4])
程序段执行后，输出的结果不可能是(　　)
A.[34, 26, 21, 19] B.[34, 26, 21, 17]
C.[34, 26, 17, 19] D.[34, 17, 19, 13]
答案　C
解析　本题考查冒泡排序算法思想。外循环i表示排序趟数，决定了有序元素的个数，内循环j决定了排序的区间和方向。从后往前冒泡，前面的数据先有序，从条件a[j] >a[j－1]来看，实现降序排列。A选项至少排4趟，B选项只排2趟，D选项未排序，C选项第1趟排序过程中，17和19要交换位置。
4.有如下Python程序段：
a＝list(map(int，input().split()))　#将输入的数据转换成列表
n＝len(a)
for i in range(2)：
　 for j in range(n－1，i，－1 )：
　 if a[j] % 3 > a[j－1] % 3：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
以下运行结果不可能的是(　　)
A.[20，50，10，40，30，60]
B.[5，8，1，3，4，6]
C.[9，17，16，4，12，5]
D.[17，11，1，4，9，6]
答案　C
解析　本题考查程序冒泡排序。从右往左(从后往前)进行了2趟排序，排序比较是元素%3后，最前面的2个元素除3余数一定是所有元素中最大的。
重难点3　冒泡排序的优化
1.列表s中包含n个互不相等的元素，用Python编程实现如下功能： s[0]到 s[n－1]降序排序，当序列已经有序时结束排序，部分代码如下。
n＝len(s)
for i in range(1，n)：
　
　for j in range()：
　 if　：
　　　　s[j]，s[j－1]＝s[j－1]，s[j]
　　　　flag ＝ True
　if flag＝＝False:
　 break
上述程序段中方框可选代码为： ①flag＝True　②flag＝False　③1，n－i＋1　④1，n－i　⑤s[j]s[j－1]，则(1)(2)(3)处代码依次为(　　)
A.②④⑥ B.②③⑥ C.①④⑤ D.①③⑥
答案　B
解析　本题考查冒泡排序算法的程序实现，着重考查冒泡排序的优化。(1)逻辑变量 flag表示该遍排序中是否有进行数据交换，没有交换提前结束排序。(2)确定每次排序时比较的范围，因外循环变量 i 的范围为[1，n)，当 i＝1 时，比较的范围应为[1，n)，当 i＝2 时，比较的范围应为[1，n－1)，以此类推，随着 i 值的增加，排序范围的终值在缩小，故填空(2)处应填入“1，n－i＋1”；(3)处确定排序方式是“升序”或“降序”，由于比较的元素为 s[j]与 s[j－1]，若要实现降序排序，应将较大值换到前面，故填空(3)处应填入“s[j]>s[j－1]”。
2.列表lst中共有n个整数，若下列程序段实现将数组元素lst[st]至lst[ed]升序排列，
while st！＝ed：
　　________________
　　for j in range(st，ed)：
　 if m[j]>m[j＋1]：
　　　　 m[j]，m[j＋1]＝m[j＋1]，m[j]
　　　　 last＝j
　　ed＝last
则划线处的代码为________________
答案　last＝st
解析　该程序实现从前往后冒泡，后面的数据先有序，ed表示无序区间的右边界，当右边界与左边界相等时，这个无序区间只剩下一个数据，该数据肯定是有序的。
重难点1　冒泡排序的算法思想
1.采用冒泡排序算法对数据序列“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。
2.采用冒泡排序算法对数据序列“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次。
3.下列代码采用冒泡排序对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个数据的升序排序。
4.小明编写程序实现数据排序功能，部分程序如下：
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选项排序为升序，与正确算法结果相同，无法检测。
5.有如下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。
6.列表中有n个互不相等的元素，即s[0]，s[1]，s[2]，……s[n－1]，有如下Python程序段：
for i in range(①________)：
　 for j in range(②________)：
　 if s[j]>s[j－1]：
　　　　s[j]，s[j－1]＝s[j－1]，s[j]
上述程序段中划线处可选代码为：
①0，n－1　②1，n－1　③1，n　④1，n－i－1　⑤1，n－i　⑥1，n－i＋1
为完成元素的排序，(1)(2)处代码依次为(　　)
A.①④ B.①⑥ C.②⑤ D.③⑥
答案　D
解析　本题考查冒泡排序的程序实现。内循环决定排序的方向的区间，从前往后冒泡，后面的数据先有序，若i的范围是[0，n－2]，则待排序的右端点为[n－1－i]，则j的range为(1，n－1－i＋1)，若i的范围是[1，n－1]，则待排序的右端点为[n－i]，则j的range为(1，n－i＋1)。从后往前冒泡，前面的数据先有序，若i的范围是[0，n－2]，则待排序的左端点为[i]，则j的range为(n－1，i＋1－1，－1)，若i的范围是[1，n－1]，则待排序的右端点为[i－1]，则j的range为(n－1，i＋1，－1)。
7.互不相等的 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])是有序的。
8.列表a包含n个互不相等的元素，依次为a[0]到a[n－1]，有如下Python程序段：
n＝6
for i in range(n－1)：
　 for j in range(n－2，i，－1)：
　 if a[j]>a[j＋1]：
　　　　 a[j], a[j＋1]＝a[j＋1], a[j]
执行该程序段后，下列说法正确的是(　　)
A.实现a[0]到a[5]的升序排序
B.总共的比较次数是10
C.总共的交换次数大于等于1
D.交换过的数据不会回到初始位置
答案　B
解析　程序实现从后往前冒泡升序排序。在第1趟排序中，第1次实现a[n－1]和a[n－2]比较和交换，最后一次实现a[2]和a[1]比较，因此程序只实现a[1]到a[5]共5个数据的排序，A选项错误。B选项共排了5趟，每趟排序比较的次数依次为4，3，2，1，共进行了10次比较。C选项若数组原始数据有序，比较次数为0。D选项若某个位置上数据比左边的大，但比右边的数据小，可以回到原始位置，如序列7，6，4中，6被换到最后，但和7比较后，又回到原来位置。
9.列表a中各元素 a[0]到 a[4]的值依次为 9, 2, 5, 1, 3，若分别执行如下两段程序，则数据交换次数分别是(　　)
程序1
for i in range(1, len(a)－1)： 　 for j in range(1, len(a)－i)： 　 if a[j－1]>a[j]： 　　　　 a[j], a[j－1]＝a[j－1]，a[j]
程序2
for i in range(len(a)－1，1，－1)： 　 for j in range(len(a)－1，len(a)－i，－1): 　 if a[j－1] > a[j]： 　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
A.1和3 B.5和5 C.5和3 D.7和7
答案　C
解析　程序实现将数组a排升序排列3次，但左侧程序排序的区间为a[0]到 a[3]，a[4]未参加排序。右侧程序排序的区间为a[1]到 a[4]，a[0]未参加排序。
10.有如下Python程序段：
a＝int(input(″输入参数a：″))
b＝int(input(″输入参数b：″))
c＝int(input(″输入参数c：″))
for i in range(a，b，c)：
　 if f[i]　 f[i]，f[i＋1]＝f[i＋1]，f[i]
print(f)
执行该程序段后，若数组f中元素值依次为“7，4，6，5，3，2”，则数组f中元素初始值不可能是(　　)
A.7，2，4，6，5，3 B.4，7，5，6，3，2
C.7，4，5，6，2，3 D.4，6，7，2，3，5
答案　D
解析　本题考查冒泡排序的算法思想。比较对象是相邻两个数，比较条件f[i]重难点2　冒泡排序的变式
1.列表a中存储了8个元素，即a[0]，a[1]，…，a[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
　　　for j in range(n－1，i，－1)：
　if a[j]　　　　a[j－1]，a[j]＝a[j]，a[j－1]
该程序段实现的是(　　)
A.a[0]到a[7]升序排序
B.a[4]到a[7]升序排序
C.a[0]到a[7]的数据对4取余之后升序排序
D.a[0]到a[3]、a[4]到a[7]分别升序排序
答案　D
解析　a[7]和a[6]、a[6]和a[5]、a[5]和a[4]依次比较，实现a[4]到a[7]升序，j为4时，并没有和a[3]比较和交换，但a[3]和a[2]、a[2]和a[1]、a[1]和a[0]依次比较和交换，形成有序序列。
2.有如下 Python 程序段：
m ＝ 3
lst ＝ [7，3，4，3，1，6，3]
for i in range(len(lst)－1)：
　 for j in range(len(lst)－1，i，－1):
　 if lst[j]　　　　 lst[j]，lst[j－1] ＝ lst[j－1], lst[j]
　
　break
执行该程序段，加框处语句被执行的次数是(　　)
A.3 B.4 C.5 D.6
答案　C
解析　本题考查冒泡排序的算法思想。提前结束排序的条件必须满足两个，其一大于等于m，其二是最后的数据与前面的数据不能相等。如要排出前3名，且有很多并列第3名(排好序[1，3，3，3，4，7，6]，需要找到4即最后一个不符合条件的数据，才能终止循环。
3.某 Python程序如下：
a＝[3，8，6，2，3]
for i in range(len(a)－1，－1，－1)：
　 if a[i]%2＝＝0：
　 for j in range(i)：
　　　　 if a[j]>a[j＋1]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
程序运行后，输出的结果是(　　)
A.[2，6，8，3，3] B.[3，3，2，6，8]
C.[2，3，6，8，3] D.[2，3，3，6，8]
答案　C
解析　本题考查冒泡排序，当a[i]是偶数时排序，因此3不参与排序，第一趟结果为[3, 8, 6, 2, 3]，再依次进行排序。
4.数组a包含10个互不相同的元素，即a[0]，a[1]，…，a[9]，其中a[0]，a[2]，…，a[8]称为奇数位元素，a[1]，a[3]，…，a[9]称为偶数位元素。有如下Python程序段：
n＝len(a)
for i in range(n∥2－1)：
　 for j in range(n－2，2*i，－2)：
　 if a[j]　　　　 a[j]，a[j－2]＝a[j－2]，a[j]
该程序段实现的功能是(　　)
A.仅对奇数位元素升序排列
B.仅对偶数位元素升序排列
C.奇数位元素升序，偶数位元素降序排列
D.奇数位元素降序，偶数位元素升序排列
答案　A
解析　本题考查冒泡排序算法思想。外循环决定排序趟数，内循环决定排序方向和区间，内循环初值为n－2，步长为负2，因此仅对奇数位置排序。
5.有如下Python程序段：
from random import randint
n＝8
L＝[randint(10, 99) for i in range(n)]
for i in range(n－1)：
　 for j in range(i＋2，len(L)，2)：
　 if i%2＝＝1 and L[i]>L[j] or i%2＝＝0 and L[i]　　　　 L[i]，L[j]＝L[j]，L[i]
执行以上程序段，数组L的值不可能的是(　　)
A.[93，15，60，62，40，65，16，90]
B.[80，20，79，41，19，88，18，99]
C.[50，84，44，39，41，50，19，11]
D.[96，11，69，16，29，46，28，80]
答案　C
解析　本题考查冒泡排序算法。算法实现偶数位升序，奇数位降序排列。
6.有如下Python程序段：
s＝″ccbbac″
a＝[i for i in range(6)]
for i in range(5)：
　 for j in range( 5－i)：
　 if s[a[j]]>s[a[j＋1]]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
运行该程序段输出的结果为(　　)
A.[4，3，2，5，1，0] B.[4，5，3，2，1，0]
C.[4，2，3，0，1，5] D.[4，3，2，5，0，1]
答案　C
解析　本题考查索引排序。数组a存储的0－5的索引位置，程序实现从前往后冒泡，当条件s[a[j]]>s[a[j＋1]]成立时交换，实现升序排列，因此排序后的结果是abbccc，找到这些字母的索引位置。
7.小明对某校立定跳远测试成绩进行排序，要求女生在前，男生在后，同性别按成绩降序排序。实现功能的Python程序如下：
a＝[[″俞凯睿″，235，'男']，[″张佳妮″，210，'女']，[″王静怡″，220，'女']，[″顾筱杨″，260，'男']，[″李臣武″，250，'男']，[″陈丹祺″，230，'女']，[″李鸿慧″，240，'女']]
n＝len(a)
for i in range(n－1)：
　 for j in range(①________)：
　 if int(a[j][1]) > int(a[j－1][1]) and a[j][2] ＝＝ a[j－1][2]：
　 a[j]，a[j－1] ＝ a[j－1]，a[j]
　 elif　②________ ：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
为完成元素的排序，①②处代码依次为(　　)
A.①1，n－i－1
②a[j][2]＝＝″女″ and a[j－1][2]＝＝″男″
B.①n－1，i，－1
②a[j][2]＝＝″男″ and a[j－1][2]＝＝″女″
C.①1，n－i
②a[j][2]＝＝″女″ and a[j－1][2]＝＝″男″
D.①n－1，i＋1，－1
②a[j][2]＝＝″男″ and a[j－1][2]＝＝″女″
答案　C
解析　本题考查冒泡排序算法思想。①排序的方向和区间。若从前往后排序，后面的数据先有序，第i趟排序的区间为[0，n－1－i]，比较对象位置为j和j－1，因此range的初值为1，终值为n－1－i＋1。若从后往前排序，前面的数据先有序，第i趟排序的区间为[n－1，i]，，因此range的初值为n－1，终值为i＋1－1，步长为－1。②交换的条件。要求女生在前，男生在后，同性别按成绩降序排序。女生在后，男生在前需进行交换。
8.数组a中存储着全校学生的学号和BMI信息，格式为[['0101'，19.2]，['0102'，18.5]，['0103'，20.1]，...]。 其中每条数据的第一项为学号，第二项为BMI值。数组a已经按学号升序排序，现要求按照BMI值进行降序排序，BMI相同情况下仍然按照学号保持升序。则下列程序段可以实现该功能的是(　　)
A.for i in range(1，n)：
　　 for j in range(n－i)：
　 if a[j＋1] > a[j]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
B.for i in range(1，n)：
　　 for j in range(n－i)：
　 if a[j][1] > a[j＋1][1]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
C.for i in range(1, n)：
　　 for j in range(n－1, i－1, －1)：
　 if a[j][1] <＝ a[j－1][1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
D.for i in range(1, n)：
　　 for j in range(n－1, i－1, －1)：
　 if a[j][1] > a[j－1][1]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
答案　D
解析　本题考查冒泡排序算法实现。A 选项比较的关键字应为：if a[j＋1][1]>a[j][1]。B 选项实现降序排序。C 选项题干要求 BMI 相同的情况下仍然按照学号保持升序，加了等号学号大的会排在前面。
9.小明编写 Python程序对本校跳高测试成绩进行排序，规则如下：按照性别分别对成绩进行降序排序并输出名次(女生排前，男生排后，同分同名次)，计算结果如图所示
(1)程序中加框处代码有错，请改正。
(2)请在划线处填入合适的代码。
#把文件中的原始数据导入到数组a中，其中a[0][0]存储姓名，a[0][1]存储跳高成绩，a[0][2]存储性别，a[1][0]到a[1][2]存储第一位学生的相关信息，以此类推。代码略
for i in range(1，①________)：
　　　for j in range(1，len(a)－i)：
　if int(a[j][1])　　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
elif
　　　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
a[1][3]＝1
for i in range(2，len(a)):
　 if a[i][1]！＝a[i－1][1]：
a[i][3]＝i
　 else：
②________
t＝0
for i in range(1，len(a)):
　 if a[i][2]＝＝″女″：
③________
　 else：
a[i][3]＝a[i][3]－t
#输出数据 a 到文件中，代码略
答案　(1)a[j＋1][2]＝＝″女″ and a[j][2]＝＝″男″　(2)①len(a)－1　②a[i][3]＝a[i－1][3]　③t＝t＋1或t＋＝1
解析　本题考查双关键字排序和顺序查找算法。(1)先按照性别和成绩进行降序排序，发生数据交换的情况有两种情况：一是性别相同，成绩大的后，二是男生在前，女生在后。a[0][1]存储跳高成绩， a[0][2]存储性别，条件“int(a[j][1])重难点3　冒泡排序的优化
1.有如下Python程序段：
d＝[12，8，6，3，8，10]
i＝0；q＝0；flag＝False
while i　 flag＝True
　　for j in range(len(d)－1，q，－1):
　　 ：
　　　d[j]，d[j－1]＝d[j－1]，d[j]
　　　 q＝j
　　　 flag＝False
　　i＝i＋1
程序运行后，加框处语句执行次数为(　　)
A.15 B.12 C.9 D.8
答案　C
解析　程序实现从后往前降序排序，q记录有序数据的个数，第1趟比较了5次，第2趟比较了3次，d的值为[12，10，8，8，6，3]，q的值为4，排序后，数据有序，第3趟只比较1次，数据无交换，结束排序，比较次数分别为5＋3＋1＝9.
2.有如下Python程序段：
d＝[11，9，23，4，8，10, 9，7]
n＝len(d)
p＝q＝0；cnt＝0
for i in range(1, n)：
　 cnt＝cnt＋1
　 for j in range(n－1，p，－1)：
　 if d[j]>d[j－1]：
　　　 d[j], d[j－1]＝d[j－1], d[j]
　　　 p＝j
　 if q＝＝p：
　 break
　 q＝p
print(cnt)
运行该程序段后，变量cnt 的值为(　　)
A.8 B.7 C.6 D.5
答案　D
解析　从后往前冒泡排序，前面的数据先有序，p记录最后一次交换的位置，如果一趟中没有数据交换，则排序结束。变量cnt统计排序趟数。
3.有如下 Python 程序段：
a＝[19，17，6，9，8]
n＝len(a)
f＝True；i＝4；k＝0
while i>0 and f：
　 f＝False
　　for j in range(i):
　 if a[j]　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 k＝k＋1；f＝True
　　i＝i－1
该程序段执行后，下列说法正确的是(　　)
A.数组a各元素的值是：6 8 9 17 19
B.变量k的值为 3
C.数组元素6在此过程中共交换了3次
D.变量i的值为 2
答案　D
解析　 本题考查冒泡排序算法。相邻两个数据a[j]第二部分　算法与程序设计
专题11　排序算法
1.了解冒泡排序本质是相邻两个数进行比较和交换，让较大的数“下沉(上冒)”，较小的数“上冒(下沉)”的一种排序技术；
2.写出每趟排序的结果，掌握每趟的比较次数、每趟的排序区间和每趟排序实现的功能；
3.列出排序序列中的逆序对，掌握总共需要的交换次数；
4.外循环实现排序的趟数，内循环决定排序的方向和区间，比较条件决定排序的方式；
5.根据外循环变量i，画出待排序区间，在待排序区间的两端写出4个比较的位置，从而确定内循环的初始和结束位置.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
冒泡排序的特征是相邻两个对象进行比较和交换，可以从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。当某趟排序过程中没有发生数据交换，表示整个序列数据有序，可以提前结束排序。冒泡排序可以用双重循环来实现，其算法复杂度为O(n2)，外循环表示循环的趟数，内循环实现第i趟排序的方向和区间，比较语句实现了升降序的方式。
真题再现
2
A
解析　本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1，5]，条件s[j]>s[j－1]表示当后一个数大于前一个数时要发生交换，实现降序排列。参加排序元素仅s[0]～s[5]。
考点精练
3
重难点1　冒泡排序的算法思想
从前往后冒泡，实现后面数据先有序，也可以从后往前冒泡，实现前面数据先有序。排序往往先找出一列数中的最值，将这个最值交换到该列数的末端，把数列划分为有序区间和无序区间，把这个操作称为一趟排序。再对无序区间进行重复操作，不断地扩大有序区间，缩小无序区间，当无序区间中只有一个数据时，全部数据有序，结束排序。排序基本算法思想是迭代执行一趟排序，直到数据全部有序。内循环的步长为正数，表示从前往后冒泡，负数表示从后往前冒泡，步长大于1，表示对局部数据进行排序。外循环次数决定排序的趟数，n个数据最多需要n－1趟排序，实现全部数据有序。内循环的初值和终值决定待排序(无序)区间的两个端点。
A
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 加框处语句表示交换次数，从条件s[j]D
解析　本题考查冒泡排序的算法实现。当条件s[j]C
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 从前往后冒泡排序，后面的数据先有序，每趟待排序区右端点将则缩小。第一趟排序时，变量i的值为st，有序的索引位置为ed，若j要取到ed－1，则终值须为ed＋st－i－1，由于range是左闭右开的区间，因此终值为ed＋st－i
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。
重难点2　冒泡排序的变式
外循环次数决定排序的趟数，从前往后冒泡，则后面部分数据有序，从后往前冒泡，则前面部分数据有序。利用这一特性，可以筛选达到要求的数据，提前结束排序。排序对象若为a[j]和a[j＋2]，则实现奇偶位分组排序。比较语句的大于或小于号决定了升降序的方式。当排序的条件有两个或多个时，或者出现了多分支的选择结构，实现的多关键字排序。
思维点拨
明考向 本题考查冒泡排序的算法实现
精点拨 ①排序的方向和区间。成绩从高到低录取考生，需进行降序排列，实现前面的数据先有序，因此需从后往前冒泡。第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
A
解析　本题考查冒泡排序的算法实现。从后往前冒泡降序排序，前面的数据先有序，一共排了3趟，因此把最大的3个数据推到最左边。
C
思维点拨
明考向 本题考查双关键字冒泡排序
精点拨 程序实现从前向后冒泡，第一关键字③：第j个比j＋1个成绩小则交换。第二关键字②⑥：第j个和第j＋1个成绩相同且第j个考号比第j＋1个大则交换
A
解析　本题考查冒泡排序的算法思想。内循环j，初值为n－2＝8，步长为－2，因此j的值为8至2的偶数。比较对象也是这些位置中的数，因此仅实现这些数的升序排列。
重难点3　冒泡排序的优化
在排序过程中，若某趟排序没有发生数据交换，意味着数据已经有序，可以提前结束排序。外循环表示排序的趟数，同时也可以表示数据有序的位置。若实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。如原始数据为6，7，8，6，6，5，4，3，2，1，第一趟排序最后一次发生交换是a[1]和a[2]，有序位置索引号为2，下趟排序中只要包含位置1即可。
B
思维点拨
明考向 本题考查冒泡排序的算法思想及算法的优化
精点拨 从内循环来看，实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。第1趟结果为[6，4，9，3，2，1]，下趟排序终点为4；第2趟结果为[6，9，4，3，2，1]，下趟排序终点为1；第3趟结果为[9，6，4，3，2，1]，下趟排序终点为0
B
解析　本题考查冒泡排序的算法实现及算法的优化。变量c统计冒泡排序的排序趟数。程序实现从后向前升序排列，d[j]和d[j－1]比较，d[j－1]先有序，因此j是无序区间的开始位置。flag变量的作用是本趟排序数据是否有交换，若没有交换，直接退出循环，否则用变量last记录无序区间的开始位置。
当堂检测
4
重难点1　冒泡排序的算法思想
重难点2　冒泡排序的变式
重难点3　冒泡排序的优化
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选项不管从哪个方向进行依次比较，都不符合。
A
解析　本题考查冒泡排序。对数据序列“4，7，3，2，8”进行冒泡，注意默认冒泡为从后往前冒。第一趟：“8，4，7，3，2”，交换4次，第二趟：“8，7，4，3，2”，交换1次。完成排序，共5次。
2.采用冒泡排序算法对数据序列“4，7，3，2，8”完成降序排序，则需交换的次数为(　　)
A.5 B.6 C.8 D.10
A
解析　考查冒泡排序算法思想。算法实现从左往右降序排列。A选项例如某个数后面有2个数，且一个数大他小，一个数比他大，当大的数往前交换后，第2次比他小的数又换回来了。总的比较次数为n*(n－1)/2＝15。D选项如果原数据已经有序了，不会发生交换。
C
解析　本题考查冒泡排序的变形。根据 if 条件s[j]＝＝'a' and s[j－1]！＝'a'可以看出，取字符串 s 中字符时，若当前字符 s[j]为'a'但 s[j－1]不为'a'，交换 s[j－1]与 s[j]的位置。因此，该程序段的功能为将字符'a'前移，其他字符保持原位置不变，交换后的结果为C.['a', 'a', 'a', 'b', 'c', 'b', 'c']。
C
解析　本题考查冒泡排序算法思想。从后往前冒泡，前面的数据先有序，有序区间的左端点是i＋1，比较对象是s[j]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。
C
解析　本题考查双关键字排序。数组a中数据升序，当a数组中值相等时，以b数组对应的值为依据，即b数组中数据降序。 数组a中最小有2个2，b数组分别对应为7和4，b中7排在前面。
C
解析　本题考查冒泡排序算法思想。外循环i表示排序趟数，决定了有序元素的个数，内循环j决定了排序的区间和方向。从后往前冒泡，前面的数据先有序，从条件a[j] >a[j－1]来看，实现降序排列。A选项至少排4趟，B选项只排2趟，D选项未排序，C选项第1趟排序过程中，17和19要交换位置。
C
解析　本题考查程序冒泡排序。从右往左(从后往前)进行了2趟排序，排序比较是元素%3后，最前面的2个元素除3余数一定是所有元素中最大的。
B
解析　本题考查冒泡排序算法的程序实现，着重考查冒泡排序的优化。(1)逻辑变量 flag表示该遍排序中是否有进行数据交换，没有交换提前结束排序。
(2)确定每次排序时比较的范围，因外循环变量 i 的范围为[1，n)，当 i＝1 时，比较的范围应为[1，n)，当 i＝2 时，比较的范围应为[1，n－1)，以此类推，随着 i 值的增加，排序范围的终值在缩小，故填空(2)处应填入“1，n－i＋1”；(3)处确定排序方式是“升序”或“降序”，由于比较的元素为 s[j]与 s[j－1]，若要实现降序排序，应将较大值换到前面，故填空(3)处应填入“s[j]>s[j－1]”。
答案　last＝st
2.列表lst中共有n个整数，若下列程序段实现将数组元素lst[st]至lst[ed]升序排列，
while st！＝ed：
　 　________________
　 　for j in range(st，ed)：
　 if m[j]>m[j＋1]：
　　 　　 m[j]，m[j＋1]＝m[j＋1]，m[j]
　　 　　 last＝j
　　ed＝last
则划线处的代码为________________
解析　该程序实现从前往后冒泡，后面的数据先有序，ed表示无序区间的右边界，当右边界与左边界相等时，这个无序区间只剩下一个数据，该数据肯定是有序的。
课后练习
5
重难点1　冒泡排序的算法思想
重难点2　冒泡排序的变式
重难点3　冒泡排序的优化
1.采用冒泡排序算法对数据序列“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。
2.采用冒泡排序算法对数据序列“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次。
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个数据的升序排序。
D
解析　实现从后往前冒泡升序排列，前面的数据先有序，但右端没有固定，每趟都在缩减，因此有些数据是排不到的。AB选项排序后均为5，6，9，8，无序，可以检测。C选项排序后为5，8，9，6，无序，可以检测。D选项排序为升序，与正确算法结果相同，无法检测。
C
解析　外循环控制排序的次数，也与排序的区间位置有关。，冒泡排序必须是一端固定，另一端随着排序的过程将不断地缩短。若从前往后冒泡，则排序的初值必须为a，第一趟排序的区间是最长的，此时i的值为0，最后位置为b，而j＋1到过b时，j的值为b－1，若要取到b－1，则终值必须为b，结合i的值，终值为b－i。
D
解析　本题考查冒泡排序的程序实现。内循环决定排序的方向的区间，从前往后冒泡，后面的数据先有序，若i的范围是[0，n－2]，则待排序的右端点为[n－1－i]，则j的range为(1，n－1－i＋1)，若i的范围是[1，n－1]，则待排序的右端点为[n－i]，则j的range为(1，n－i＋1)。从后往前冒泡，前面的数据先有序，若i的范围是[0，n－2]，则待排序的左端点为[i]，则j的range为(n－1，
i＋1－1，－1)，若i的范围是[1，n－1]，则待排序的右端点为[i－1]，则j的range为(n－1，i＋1，－1)。
C
解析　本题考查冒泡排序算法思想。分析冒泡排序内循环的代码，是从左(前)向右(后)冒泡、降序。外循环只进行了5次，所以只有最后5个数(s[5]到 s[9])是有序的。
B
解析　程序实现从后往前冒泡升序排序。在第1趟排序中，第1次实现a[n－1]和a[n－2]比较和交换，最后一次实现a[2]和a[1]比较，因此程序只实现a[1]到a[5]共5个数据的排序，A选项错误。B选项共排了5趟，每趟排序比较的次数依次为4，3，2，1，共进行了10次比较。C选项若数组原始数据有序，比较次数为0。D选项若某个位置上数据比左边的大，但比右边的数据小，可以回到原始位置，如序列7，6，4中，6被换到最后，但和7比较后，又回到原来位置。
9.列表a中各元素 a[0]到 a[4]的值依次为 9, 2, 5, 1, 3，若分别执行如下两段程序，则数据交换次数分别是(　　)
程序1
for i in range(1, len(a)－1)：
　 for j in range(1, len(a)－i)：
　 if a[j－1]>a[j]：
　　　　 a[j], a[j－1]＝a[j－1]，a[j]
程序2
for i in range(len(a)－1，1，－1)：
　 for j in range(len(a)－1，len(a)－i，－1):
　 if a[j－1] > a[j]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
A.1和3 B.5和5 C.5和3 D.7和7
C
解析　程序实现将数组a排升序排列3次，但左侧程序排序的区间为a[0]到 a[3]，a[4]未参加排序。右侧程序排序的区间为a[1]到 a[4]，a[0]未参加排序。
D
解析　本题考查冒泡排序的算法思想。比较对象是相邻两个数，比较条件f[i]D
解析　a[7]和a[6]、a[6]和a[5]、a[5]和a[4]依次比较，实现a[4]到a[7]升序，j为4时，并没有和a[3]比较和交换，但a[3]和a[2]、a[2]和a[1]、a[1]和a[0]依次比较和交换，形成有序序列。
C
解析　本题考查冒泡排序的算法思想。提前结束排序的条件必须满足两个，其一大于等于m，其二是最后的数据与前面的数据不能相等。如要排出前3名，且有很多并列第3名(排好序[1，3，3，3，4，7，6]，需要找到4即最后一个不符合条件的数据，才能终止循环。
C
解析　本题考查冒泡排序，当a[i]是偶数时排序，因此3不参与排序，第一趟结果为[3, 8, 6, 2, 3]，再依次进行排序。
A
解析　本题考查冒泡排序算法思想。外循环决定排序趟数，内循环决定排序方向和区间，内循环初值为n－2，步长为负2，因此仅对奇数位置排序。
C
解析　本题考查冒泡排序算法。算法实现偶数位升序，奇数位降序排列。
C
解析　本题考查索引排序。数组a存储的0－5的索引位置，程序实现从前往后冒泡，当条件s[a[j]]>s[a[j＋1]]成立时交换，实现升序排列，因此排序后的结果是abbccc，找到这些字母的索引位置。
C
解析　本题考查冒泡排序算法思想。①排序的方向和区间。若从前往后排序，后面的数据先有序，第i趟排序的区间为[0，n－1－i]，比较对象位置为j和j－1，因此range的初值为1，终值为n－1－i＋1。若从后往前排序，前面的数据先有序，第i趟排序的区间为[n－1，i]，，因此range的初值为n－1，终值为i＋1－1，步长为－1。②交换的条件。要求女生在前，男生在后，同性别按成绩降序排序。女生在后，男生在前需进行交换。
答案　D
解析　本题考查冒泡排序算法实现。A 选项比较的关键字应为：if a[j＋1][1]>a[j][1]。B 选项实现降序排序。C 选项题干要求 BMI 相同的情况下仍然按照学号保持升序，加了等号学号大的会排在前面。
9.小明编写 Python程序对本校跳高测试成绩进行排序，规则如下：按照性别分别对成绩进行降序排序并输出名次(女生排前，男生排后，同分同名次)，计算结果如图所示
答案　(1)a[j＋1][2]＝＝″女″ and a[j][2]＝＝″男″　(2)①len(a)－1　
②a[i][3]＝a[i－1][3]　③t＝t＋1或t＋＝1
解析　本题考查双关键字排序和顺序查找算法。(1)先按照性别和成绩进行降序排序，发生数据交换的情况有两种情况：一是性别相同，成绩大的后，二是男生在前，女生在后。a[0][1]存储跳高成绩， a[0][2]存储性别，条件“int(a[j][1])文字，因此共有len(a)－1条记录，当第len(a)－2条记录有序时，整个列表已经有序了，因此①处答案为len(a)－1。接下来按成绩进行对全体学生名次进行赋值，语句a[1][3]＝1表示成绩最高的第1位女生排名为1，条件a[i][1]！＝a[i－1][1]成立，表示该学生与前面一位学生成绩不相同，他的名次号就是当前序号，如果成绩相同，名次与前一位学生名次相同，因此②处答案a[i][3]＝a[i－1][3]。男生名次号是紧跟在女生后面赋值的，条件a[i][2]＝＝″女″表示当前记录为女生，如果该条件不成立，表示男生的名次值，a[i][3]＝a[i][3]－t，t为女生的人数，因此③处将对女生进行计数，答案为t＝t＋1。
C
解析　程序实现从后往前降序排序，q记录有序数据的个数，第1趟比较了5次，第2趟比较了3次，d的值为[12，10，8，8，6，3]，q的值为4，排序后，数据有序，第3趟只比较1次，数据无交换，结束排序，比较次数分别为5＋3＋1＝9.
D
解析　从后往前冒泡排序，前面的数据先有序，p记录最后一次交换的位置，如果一趟中没有数据交换，则排序结束。变量cnt统计排序趟数。
D
解析　本题考查冒泡排序算法。相邻两个数据a[j]

展开更多......

收起↑