资源简介

(共84张PPT)
课时3　数据排序
第五章　数据结构与算法
1.通过具体实例，理解排序的概念和基本方法。2.能根据实际的应用场景，选择合理的数据结构，并使用排序算法来编程解决问题。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.排序
(1)排序的概念
排序是指将一些______的数据变成______的数据。
(2)排序方式
排序方式主要有：______(从小到大排列)和______(从大到小排列)。
(3)待排数据的存储方式
待排数据通常存储在数组或链表中。
无序
有序
升序
降序
2.常见的排序算法
常见的排序方法有：____________、____________、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。
冒泡排序
选择排序
3.利用Python的sort方法和内建函数sorted排序
(1)sort方法
说明：使用sort方法对列表中的数据进行排序时，将______对列表进行排序，不会产生______列表。
例：列表lista＝[36，23，12，17，22，19，28]，可用命令lista.sort()将列表lista中的数据进行升序排序，可用命令lista.sort(reverse＝True) 将列表lista中的数据进行降序排序。
直接
新的
(2)sorted函数
说明：使用sorted函数进行排序时，将排好序的数据返回一个____________。
例：lista＝[36，23，12，17，22，19，28]，执行语句listb＝sorted(lista)后，列表listb中的元素为[12，17，19，22，23，28，36，]，从而实现升序排序；执行语句listc＝sorted(lista，resverse＝True)后，列表listc中的元素为[36，28，23，22，19，17，12]，从而实现降序排序。
新的序列
4.冒泡排序
(1)冒泡排序的基本思想
冒泡排序是在数列中对______两个数据依次进行______和位置调整，让较大的数“下沉(或上冒)”，较小的数据“上冒(或下沉)”的一种排序技术。
(2)冒泡排序的特点
①______两个数据进行比较。
②n个数据完成排序，共进行_________趟(遍)排序。
④n个数据完成排序，其时间复杂度为___________。
相邻
比较
相邻
n－1
O(n2)
5.冒泡排序算法的程序实现
说明：对列表list1中的数据进行升序排序
def bubble_sort(list1)：
count＝len(list1)
#count个数排序共需进行count－1趟
for i in range(1，count)：
#每一趟排序从前往后进行，比较相邻两个数
for j in range(_______________)：
　　　　　　if _____________________：
　　　　　list1[j]，list1[j＋1]＝list1[j＋1]，list1[j]
return list1
0，count－i
list1[j]>list1[j＋1]
(1)冒泡排序进行时，数据的比较可以由前往后进行，即list1[j]与listl[j＋1]比较；也可以由后往前进行，即list1[j]与list1[j－1]比较，此时应将循环条件“for j in range(0，count－i)：”修改为“for j in range(count－1，i－1，－1)：”。
(2)若要将数据按降序排列，只需将语句“if list1[j]>list1[j＋1]：”修改为“if list1[j]例题精析
2
例1 采用冒泡排序算法对数据序列“21，15，23，26，33，18，46，17”完成升序排序，理论上讲共需进行排序的遍数为(　　)
A.3遍 B.4遍 C.7遍 D.8遍
C
解析　共有8个数据，共需要进行7遍排序， 因此答案为C。
变式训练　采用冒泡排序算法对数据序列“16，11，8，9，21，32，28”完成升序排序，共进行数据交换的次数为(　　)
A.3次 B.4次 C.5次 D.6次
解析　本题主要考查的是冒泡排序思想。排序过程如下：
D
原始数据 16，11，8，9，21，32，28 交换次数
第1遍完成后的数据为 8，16，11，9，21，28，32 交换3次
第2遍完成后的数据为 8，9，16，11，21，28，32 交换2次
第3遍完成后的数据为 8，9，11，16，21，28，32 交换1次
第4遍完成后的数据为 8，9，11，16，21，28，32 不交换
… … 不交换
因此，完成升序排序，共交换的次数为6次，答案为D。
例2 采用冒泡排序算法对8个数据“48，65，29，16，22，75，36，41”进行降序排序，则第3遍的排序结果是(　　)
A
原始数据 48，65，29，16，22，75，36，41
第1遍完成后的数据为 75，48，65，29，16，22，41，36
第2遍完成后的数据为 75，65，48，41，29，16，22，36
第3遍完成后的数据为
A.75，65，48，41，36，29，16，22
B.75，65，48，41，29，16，22，36
C.75，65，48，41，36，29，22，16
D.75，65，48，41，29，22，16，36
解析　本题主要考查的是冒泡排序的实现。根据第1、2遍可知，冒泡排序是从后往前进行降序排序，根据第2遍的结果可推出第3遍的排序结果为75，65，48，41，36，29，16，22，因此，答案为A。
变式训练　小明对6个数字“3，5，8，2，6，1”进行两遍冒泡排序后的数字序列设置为办公室门的密码锁，则该密码可能是(　　)
①1 2 3 5 8 6　②8 6 3 5 2 1　③1 2 3 5 6 8
④3 2 5 1 6 8　⑤8 5 6 3 2 1
A.①②③④⑤ B.①②
C.④⑤ D.①②④⑤
解析　本题主要考查的是冒泡排序思想。排序方式有升序和降序，排序的方向可以从前往后或从后往前，因此要分4种情况进行讨论分析。如果是升序排序，从前往后进行两遍后数据序列为②，从后往前进行两遍后数据序列为①；如果是降序排序，从前往后进行两遍后数据序列为⑤，从后往前进行两遍后数据序列为④。因此，①②④⑤都有可能，答案为D。
D
例3 列表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
变式训练　有如下Python程序段：
C
b＝[17，8，6，15，21，36，18，33]
n＝len(b)
for i in range(1，4)：
for j in range(n－1，i－1，－1)：
if b[j]>b[j－1]：
　　　b[j]，b[j－1]＝b[j－1]，b[j]
经过该程序段“加工”后，列表b中的元素为(　　)
A.[36，33，17，8，6，15，21，18]
B.[36，33，21，17，15，8，6，18]
C.[36，33，21，17，8，6，15，18]
D.[36，33，21，18，17，8，6，15]
解析　本题主要考查的冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法进行降序排序3遍，数据比较是从后往前进行的，进行第1遍排序后的数据序列为[36，17，8，6，15，21，33，18]，进行第2遍排序后的数据序列为[36，33，17，8，6，15，21，18]，进行第3遍排序后的数据序列为[36，33，21，17，8，6，15，18]，因此答案为C。
例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]
解析　实现从后往前冒泡升序排列，前面的数据先有序，但右端没有固定，每趟都在缩减，因此有些数是排不到的。AB选项排序后均为5，6，9，8，无序，可以检测。C选项排序后为5，8，9，6，无序，可以检测。D选项排序为升序，与正确算法结果相同，无法检测。
D
变式训练　有如下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):
程序运行后，加框处语句执行次数为(　　)
A.15 B.12 C.9 D.8
解析　程序实现从后往前降序排序，q记录有序数据的个数，第1趟比较了5次，第2趟比较了3次，d的值为[12，10，8，8，6，3]，q的值为4，排序后，数据有序，第3趟只比较1次，数据无交换，结束排序，比较次数分别为5＋3＋1＝9。
C
随堂检测
3
1.采用冒泡排序算法对数据序列“9，7，6，8，5，4，2，3”进行升序排序，约定从前往后进行数据比较及位置交换，则第2趟排序结束时的数据序列为(　　)
A.7，6，8，5，4，2，3，9 B.6，7，5，4，2，3，8，9
C.6，5，4，2，3，7，8，9 D.6，7，4，2，3，5，8，9
B
解析　第1趟排序结束时的数据序列为7，6，8，5，4，2，3，9，第2趟排序结束时的数据序列为6，7，5，4，2，3，8，9。 因此，答案为B。
2.采用冒泡排序算法对数据序列“6，8，9，5，4，2，7，3”进行降序排序，约定从后往前进行数据比较及位置交换，则进行第2趟排序时的数据交换次数为(　　)
A.0次 B.1次 C.2次 D.3次
C
解析　第1趟排序结束时的数据序列为9，6，8，7，5，4，2，3，数据交换5次，第2趟排序结束时的数据序列为9，8，6，7，5，4，3，2，数据交换2次，因此答案为C。
3.有如下Python程序段：
C
b＝[99，88，77，66，55，61，71，81]
count＝len(b)
for i in range(1，4)：
for j in range(0，count－i)：
　　 　if b[j]>b[j＋1]：
　　　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
经过该程序段“加工”后，列表b中的元素为(　　)
A.[77，66，55，61，71，81，88，99] B.[55，61，66，71，77，81，88，99]
C.[66，55，61，71，77，81，88，99] D.[66，61，55，71，77，81，88，99]
解析　本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法进行升序排序3遍，数据比较是从前往后进行的，第1遍排序后列表b中的元素为[88，77，66，55，61，71，81，99]，第2遍排序后的数据序列为[77，66，55，61，71，81，88，99]，第3遍排序后的数据序列为[66，55，61，71，77，81，88，99]，因此答案为C。
4.有如下Python程序段：
A
解析　加框处语句表示交换次数，从条件s[j]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
5.有如下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 key　 　　a[j＋1]＝a[j]
　　 　j－＝1
　　　a[j＋1]＝key
B
A.[3，6，8，10，12] B.[1，5，8，9，12]
C.[6，10，10，12，12] D.[8，9，10，10，12]
解析　本题考查排序算法和随机数函数。首先列表a中的初始值是[1，10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a的合适位置上，使得列表a的值非降序排列，因此选项A、C、D都是有可能的。
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)
C
运行该程序段输出的结果为(　　)
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]
解析　本题考查索引排序。数组a存储的0－5的索引位置，程序实现从前往后冒泡，当条件s[a[j]]>s[a[j＋1]]成立时交换，实现升序排列，因此排序后的结果是abbccc，找到这些字母的索引位置。
7.有如下Python程序：
A
解析　从后往前冒泡，排了3趟。
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]
8.有如下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)
C
若要实现列表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。
9.有如下Python程序段：
a＝[3，8，6，2，1，0，7]
n＝len(a)
for i in range((n－1)∥2):
　j＝0；k＝1
　 while j　　 if a[j]*k>a[j＋2]*k:
　　　 a[j]，a[j＋2]＝a[j＋2]，a[j]
　　　j＝j＋1；k＝－k
A
执行该程序段，则a[4：7]的值为(　　)
A.6，0，7 B.6，7，8 C.3，8，1 D.6，8，7
解析　当k为1时，a[j]>a[j＋2]表示升序排序，k为－1时，降序排序；程序实现奇位升序，偶位降序排列。
4
巩固与提升
基础巩固
能力提升
A.使用冒泡排序算法完成n个数据的排序，共需要进行n－1趟
B.冒泡排序是通过比较相邻两个元素的大小和位置交换来完成的
C.冒泡排序进行时，相邻元素的比较和交换只能从前往后进行
D.使用冒泡排序算法完成6个数据的排序，最坏情况下，数据交换次数为15次
C
解析　冒泡排序进行时，相邻元素的比较和交换可以从前往后进行，也可以从后往前进行，因此答案为C。
2.采用冒泡排序算法完成数据序列“9，8，7，6，5，2，3，4”的升序排序，则数据交换的次数为(　　)
A.18次 B.22次 C.25次 D.27次
C
解析　例如排序方向从前往后进行，排序过程如下：
原始数据 9，8，7，6，5，2，3，4 交换次数
第1遍完成后的数据为 8，7，6，5，2，3，4，9 交换7次
第2遍完成后的数据为 7，6，5，2，3，4，8，9 交换6次
第3遍完成后的数据为 6，5，2，3，4，7，8，9 交换5次
第4遍完成后的数据为 5，2，3，4，6，7，8，9 交换4次
第5遍完成后的数据为 2，3，4，5，6，7，8，9 交换3次
第6遍完成后的数据为 2，3，4，5，6，7，8，9 不交换
第7遍完成后的数据为 2，3，4，5，6，7，8，9 不交换
排序完成时，共进行7＋6＋5＋4＋3＝25次，因此，答案为C。
3.有8个学生的体重(单位：公斤)依次为“50.5，60.8，65.6，80.8，48.5，52.1，61.3，70.2”，若采用冒泡排序算法对其进行升序排序，则第3遍的排序结果是(　　)
D
原始数据 50.5，60.8，65.6，80.8，48.5，52.1，61.3，70.2
第1遍完成后的数据为 48.5，50.5，60.8，65.6，80.8，52.1，61.3，70.2
第2遍完成后的数据为 48.5，50.5，52.1，60.8，65.6，80.8，61.3，70.2
第3遍完成后的数据为
A.48.5，50.5，52.1，60.8，65.6，61.3，80.8，70.2
B.48.5，50.5，52.1，60.8，61.3，65.6，70.2，80.8
C.48.5，50.5，52.1，60.8，65.6，70.2，80.8，61.3
D.48.5，50.5，52.1，60.8，61.3，65.6，80.8，70.2
解析　观察第1遍和第2遍排序可知，排序是从后往前进行的，排序方式为升序，因此容易得出第3遍的排序结果为48.5，50.5，52.1，60.8，61.3，65.6，80.8，70.2，答案为D。
4.对列表b中的n个元素进行降序排序，其排序算法的Python部分程序段如下：
　b＝[34，435，23，98，788，30，77]
　n＝len(b)
　count＝0
　for i in range(0，n－1)：
for j in range(①__________)：
　　　　 if ②________________：
　　　　　　 count＝count＋1
　　　　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
　print(″排序后的序列为：″，b)
　print(″数据交换次数为：″，count)
A
程序划线①②处应填入的语句为(　　)
A.①0，n－i－1　　②b[j]B.①n－1，i，－1 ②b[j]>b[j－1]
C.①0，n－i ②b[j]D.①0，n－i－1 ②b[j]>b[j＋1]
解析　根据交换语句b[j]，b[j＋1]＝b[j＋1]，b[j]可知，排序方向为从前往后进行的，因此①处应为0，n－i－1, ②处代码为b[j]5.有如下 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
D
该程序段执行后，下列说法正确的是(　　)
A.数组a各元素的值是：6 8 9 17 19
B.变量 k 的值为 3
C.数组元素 6 在此过程中共交换了 3 次
D.变量 i 的值为 2
解析　本题考查冒泡排序算法。相邻两个数据a[j]6.有如下Python程序段：
　b＝[5，32，17，22，15，36，41，55]
　count＝len(b)
　for i in range(1，3)：
for j in range(1，count－i)：
　　　if b[j]　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
C
经过该程序段“加工”后，列表b中的元素为(　　)
A.[32，22，17，36，41，55，15，5]
B.[32，22，36，41，55，17，15，5]
C.[5，32，22，36，41，55，17，15]
D.[5，32，36，41，55，22，17，15]
解析　本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法对后7个数据进行2趟降序排序，数据比较是从前往后进行的，需注意的是列表b中的第1个元素(索引位置0)不参与排序，第1遍排序后列表b中的元素为[5，32，22，17，36，41，55，15]，第2遍排序后的数据序列为[5，32，22，36，41，55，17，15]。因此，答案为C。
7.如下 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)
C
执行该程序段后，输出的内容为(　　)
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']
解析　本题考查冒泡排序的变形。根据 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']。
A.这轮排序，有可能没发生数据交换
B.这轮排序，有可能只发生了1次数据交换
C.排序结束后，数据是升序的
D.完成全部排序后，数据交换的次数和冒泡的方向无关
A
解析　本题考查冒泡排序。经过一轮后最小数在最前面，可知，该冒泡排序是从后往前冒泡，升序。A选项原始数据最小数2不在最前面，一定会发生交换。若原始数据就是一趟排序结果，9在中间，无论是从后往前，还是从前往后，都要发生数据交换。B选项若原始数据如果为“2，3，5，9，6，7”，那么就发生了一次交换。C选项从一趟结果来看，是升序排列。D选项数据的交换取决于逆序对的个数，与排序方向无关。
9.有如下 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]
C
执行上述程序段后，a[1]与 b[1]的值分别是(　　)
A.8，7 B.7，7 C.2，4 D.2，7
解析　本题考查双关键字排序。主关键字为a数组，次关键字为b数组，当a[j]>a[j＋1]就交换数据，表示升序。当a[j]＝＝a[j＋1] and b[j]10.使用列表a 和列表b 分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i]，使用 Python 编程实现如下功能：将成绩数据“按总分降序排序、总分相同按学号升序排序”，代码如下。
n＝len(a)
for i in range(1，n)：
　 for j in range(0，n－i)：
　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
C
上述程序段中方框处可选代码为： ①a[j]>a[j＋1]
②a[j]＝＝a[j＋1]　③a[j]b[j＋1]则(1)(2)(3)处代码依次为(　　)
A.③②④ B.①⑤⑥ C.③②⑥ D.①⑤④
解析　本题考查冒泡排序。从 for j in range(0，n－i)可知，从前向后冒泡，相邻两数两两比较；比较规则如下：第 j 个比 j＋1 个成绩小则交换，选语句 ③。第 j 个和第 j＋1 个成绩相同，选语句②，且第 j 个考号比第 j＋1 个大，选语句⑥。
11.某 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]
D
下列说法正确的是(　　)
A.整个加工过程总的交换次数为 21
B.该程序段执行后，s 的值为[9，8，7，5，4，3，2]
C.若s的初始值已有序，则该算法的时间复杂度为 O(1)
D.每一遍加工中，最小的元素“上浮”
解析　本题考查排序算法。当条件s[j]12.火车调度台是实现火车车厢整理的平台，当相邻2节车厢序号不符合整理要求时，可以对调2节车厢，实现序号顺序调整。相邻2个进行符合目标的交换，和我们学习的冒泡排序思想一致，所以这个调度过程可以用冒泡排序实现。为了提高效率，对冒泡排序做了优化，请完善下列代码：
nums＝[3，1，2，4，5，6]
①____________
k＝n－1
for i in range(n－1)：
②______________
for j in range(k)：
if (nums[j]>nums[j＋1])：
　　　　　nums[j]，nums[j＋1]＝nums[j＋1]，nums[j]
　　　　　③____________
　　　　　ex_flag＝True
if ex_flag：
break
print(nums)
答案　①n＝len(nums)　②ex_flag＝False ③k＝j
解析　本题主要考查冒泡排序算法的优化。题目中实现优化的方法是，当某趟排序过程中没有发生数据的交换时，说明数据已经有序，结束数据的排序；同时，通过记录最后发生数据交换的位置，缩小数据排序的范围。空①处n＝len(nums)，获得数据的规模，空②处ex_flag＝False，当发生数据交换时，ex_flag会被赋值为True，空③处k＝j表示记录最后发生数据交换的位置。
13.小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将列表b中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的Python程序段如下，请回答下列问题。
　b＝[26，12，30，23，32，28，49，35，38]
　n＝len(b)
　for i in range(1，(n－1)∥2)：
for j in range(0，n－i*2)：
　　　　　if ①________________：
　　　 　b[j]，b[j＋2]＝b[j＋2]，b[j]
　for i in range(1，n∥2＋1)：
　 　　j＝2*i－1
　　　if b[j]　　 　　b[j]，b[j－1]＝b[j－1]，b[j]
　　　　t＝b[i]
　　　　j＝i－1
　　　　while t　　　　　b[j＋1]＝b[j]
　　　　　j－＝1
　　　　②____________________
　print(″处理后的数据序列为：″，b)
(1)加框处的代码有误，请改正。
(2)请在程序划线处填入合适的代码。
答案　(1)2，n，2　(2)①b[j]>b[j＋2] ②b[j＋1]＝t
解析　本题主要考查排序的综合应用。本题在排序过程中，使用到了冒泡排序和插入排序算法，本题的算法思想是：首先利用改进的冒泡排序分别对数列b中奇数位置和偶数位置上的元素进行升序排序，排序结束后的数据序列特点为：奇数位置上的元素已升序排列，偶数位置上的元素已升序排列；然后从第2个元素(索引位置1)开始，让偶数位置上的元素和它前面奇数位置上的元素比较，通过数据交换使得它们变为升序，此时奇偶数据对也已升序排列；
最后从第3个元素位置，将奇数位置上的元素插入到前面有序的数列中，从而实现整个数列的升序排序。因此，加框处的代码修改为2，n，2，划线①处应填入的语句为b[j]>b[j＋2]。在插入排序中需注意的是当前元素应插入的位置为j＋1，因此，划线②处应填入的语句为b[j＋1]＝t。
14.小明为了研究冒泡排序过程中数据的“移动”情况，编写了一个Python程序，功能如下：第一行显示排序前的数据，输入初始位置(即下标值)后，输出指定初始位置的数据在排序过程中的位置变化情况，最后一行输出排序后的数据。程序运行示例如图所示。
请输入初始位置(索引值)：2
排序前数据序列为：[43，23，65，12，26，33，58，19]
位置变化情况：2→1→0
排序后的数据序列为：[65，58，43，33，26，23，19，12]
实现上述功能的Python程序如下，请回答下列问题。
　a＝[43，23，65，12，26，33，58，19]
　n＝len(a)
　pos＝int(input(″请输入初始位置(索引值)：″))
　①________________
　print(″排序前数据序列为：″，a)
　for i in range(1，n)：
for j in range(0，n－i)：
if ②________________：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
if pos＝＝j：
　　pos＝j＋1
s＝s＋″→″＋str(pos)
elif ③________________：
　　　　pos＝j
　 　　　s＝s＋″→″＋str(pos)
print(″位置变化情况：″＋s)
print(″排序后的数据序列为：″，a)
(1)请在程序划线处填入合适的代码。
(2)程序运行样例如图所示，若输入的初始位置(索引值)为4，则输出的位置变化情况为__________________。
解析　本题主要考查的是冒泡排序算法的综合应用。(1)字符串s记录的是初始位置元素的位置变化情况，显然，其初值为pos，需注意的是应先将pos转换为字符串后再赋值于s，因此①处代码为s＝str(pos)；数据的比较和交换是从左往右进行的，根据运行示例可知，是进行降序排序，因此②处语句为a[j]答案　(1)①s＝str(pos)　②a[j](2)若输入的初始位置(索引值)为4，即研究列表中第5个数据(26)的位置变化，在排序过程中，26的位置变化情况为4→3→2→3→4。
15.要向可容纳88966名观众的卢赛尔球场派送外卖是一项艰巨的任务，为了方便外卖派送，将球场观众席划分为A、B、C、D、E、F、G、H共8 个区，派单平台可以根据各区域订单数量安排派送人员，以提高外卖派送效率(一个派送人员只安排一个区域)，平台根据订单总量与空闲派送人员数量计算人均派单量，按平均派单数计算各区域所需派送人员，但按此方法分配派送人员，人员总数可能超过空闲派送人员数，则删除超额派送人数，删除规则如下：每个有订单的区域至少保留一个派送人员，每个区域最多减去一个派送人员，优先删除派单尾数最少的区域中的派送人员，如果派单尾数相同，则在分配到派送人员数最多的区域中去掉一个派单人员，例如：A～H区域的订单数量分别为[468，329，392，247，38，180，263，82]，此时空闲派单人员数为30人，人均派单数为67，则各区域分配的派单人员数量分别为7、5、6、4、1、3、4、2，合计32个派送人员，需减掉2超额派送人员，即从D区和H区派送人员中各减去1个。如下表所示：
球场区域 A B C D E F G H 合计
订单数量 468 329 392 247 38 180 263 82 1999
所需派送人员 7 5 6 4 1 3 4 2 32
派单尾数 66 61 57 46 38 46 62 15 391
去除派单人员 －1 －1 －2
实际派送人员数 7 5 6 3 1 3 4 1 30
(1)数据如上表所示，如果F区退掉2份订单，重新计算并分配派送人员(整体调整)，F区派送人员的人均派单量是________。
(2)实现上述功能的Python程序如下，请在画线处填写正确的代码。
#从数据库中读取各订单所在区域，如
a＝['A'，'B'，'H'，'F'，……]
qyn＝8　　　　　　　　　　 #区域数量
psryn＝30　　　　　　　　　#配送人员数量
rs＝round(len(a)/psryn)
b＝[]
for i in range(qyn)：
　c＝chr(i＋65)　　　#A的ASCII码是65
　 b.append([c，0，0])　　　 #生成二维列表b＝[['A'，0，0]，['B'，0，0]……]
for i in a：　　　　　　 #统计各区域订单数量
　　①________
s＝0
for i in range(qyn) ：
　　②________
　　if b[i][1]%rs！＝0：
　 b[i][2]＋＝1
　s＋＝b[i][2]
k＝s－psryn
i＝0
while k>0：
　for j in range(qyn－1，i，－1)：
　if ③______：
　　　　b[j－1]，b[j]＝b[j]，b[j－1]
　　　if b[i][2]>1：
　b[i][2]－＝1
　k－＝1
　　　i＋＝1
(3)若函数中语句“s＋＝b[i][2]”缩进到了“if b[i][1]%rs！＝0：”模块内，题中所给的样例数据运行结果__________(是/否)受到影响，将样例“E”区订单数量38修改为__________能测出程序存在的问题。
答案　(1)89　(2)①b[ord(i)－65][1]＋＝1
②b[i][2]＝b[i][1]∥rs
③b[j－1][1]%rs>b[j][1]%rs or b[j－1][1]%rs＝＝b[j][1]%rs and b[j－1][2](3)否　 67或67的倍数
解析　本题考查二维数组应用和冒泡排序算法。(1)优先删除派单尾数最少区域中的派送人员，F区退掉2份订单，尾单数量为44，实际派送人员为2人，人均派单量为178/2＝89。(2)①统计各区域订单数量，从条件b[i][1]%rs！＝0来看，b[i][1]存储的是各区域的订单数量，数据库中读取各订单所在区域，需先将a数组中A－H转换成0－7的索引号，再对b数组进行累加计数。②计算所需派送人员。从语句k＝s－psryn来看，s是所需派送人员人数之和，每个区域产生尾单后，所需派送人员增加1人，因此先计算整数倍的值。③找到去除派单人员的条件。k是需去除派单人员，按尾单人数采用冒泡降序排序，找出符合条件最大的k个值，优先删除派单尾数最少的区域中的派送人员，如果派单尾数相同，则在分配到派送人员数最多的区域中去掉一个派单人员，因此是一个双关键字排序算法。(3)样题给出数据的尾单数均不为0，因此条件b[i][1]%rs！＝0始终成立，是否缩进不影响结果，只有当尾单出现为0时，影响结果。
16.学校物品室有n个箱子(箱子上分别有编号1、2、3…n)，箱子里存有数量不一的物品。有m位学生前来领取物品(物品总量足够领取)，每位学生优先从物品数量最多的箱子领取，数量不够时，再从下一个数量最多的箱子领取。小郑设计了一个程序，按箱子编号从小到大依次输入每个箱子的物品数量，依次输入每位学生需要领取物品的数量，按顺序显示每个学生领取物品的箱子编号，并显示领取结束后非空箱子的编号和剩余物品数量。运行界面如图所示。
物品数量：[12，9，5，5，3，2]
箱子编号：[4，2，1，6，5，3]
领取数量：[20，6，7，2]
第1位学生领取物品的箱子编号依次为：4　2
第2位学生领取物品的箱子编号依次为：1　6
第3位学生领取物品的箱子编号依次为：6　5
第4位学生领取物品的箱子编号依次为：3
剩余物品数量：2号箱子：1
回答下面问题：
(1)如果1号到5号箱子的物品数量分别是25，16，9，5，3，每位学生需要的物品数量分别是19，18，10，3，则第3位学生领取物品的箱子编号按顺序依次是3号、________(填整数)号。
(2)实现上述功能的程序如下，请在划线处填入合适的代码。
#依次输入物品数量存入列表a，箱子上的编号(1 到 n)依次存入列表bh，箱子数量存入变量 n，并按物品数量从多到少对箱子排序，代码略。
#依次输入学生需要领取物品的数量存入数组 b，学生人数存入变量 m，代码略
p＝0；q＝0
for i in range(m)：
num＝0
while numnum＋＝a[q]
a[q]＝0
①________________
s＝″第″＋str(i＋1)＋″位学生领取物品的箱子编号依次为：″
for j in range(p，q)：
s＋＝str(bh[j])＋″″
print(s)
if num>b[i]：
a[q－1]＝②________________
q＝q－1
for j in range(③________________): #维护非空箱子降序序列(按箱子中剩余物品数量)
if a[j]　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　 　bh[j]，bh[j＋1]＝bh[j＋1]，bh[j]
p＝q
s＝″剩余物品数量：″
for i in range(0，n)：
if a[i]>0：
　 s＝s＋str(bh[i])＋″号箱子：″＋str(a[i])
print(s)
答案　(1)1　(2)①q＝q＋1　②num－b[i] ③q，n－1
解析　(1)第1位学生在1号箱子里领取19，第2位学生在2号中领取16，在3号中领取2。剩下箱子中数量依次为6，0，7，5，3，因此第3位同学领取3号箱子和1号箱子。(2)循环for i in range(m)中，变量i表示第几个学生，他应该领取的数量为按物品数量b[i]，变量num表示他已经领取的数量，当条件num>b[i]成立时，②num－b[i]。③从多到少对箱子排序，比较对象为a[j]和a[j＋1]，因此从位置q到n－2，当j＝n－2时，j＋1达到终点。课时3　数据排序
课时目标
1.通过具体实例，理解排序的概念和基本方法。2.能根据实际的应用场景，选择合理的数据结构，并使用排序算法来编程解决问题。
1.排序
(1)排序的概念
排序是指将一些________的数据变成________的数据。
(2)排序方式
排序方式主要有：________(从小到大排列)和________(从大到小排列)。
(3)待排数据的存储方式
待排数据通常存储在数组或链表中。
2.常见的排序算法
常见的排序方法有：____________、__________、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。
3.利用Python的sort方法和内建函数sorted排序
(1)sort方法
说明：使用sort方法对列表中的数据进行排序时，将____________对列表进行排序，不会产生________列表。
例：列表lista＝[36，23，12，17，22，19，28]，可用命令lista.sort()将列表lista中的数据进行升序排序，可用命令lista.sort(reverse＝True) 将列表lista中的数据进行降序排序。
(2)sorted函数
说明：使用sorted函数进行排序时，将排好序的数据返回一个____________。
例：lista＝[36，23，12，17，22，19，28]，执行语句listb＝sorted(lista)后，列表listb中的元素为[12，17，19，22，23，28，36，]，从而实现升序排序；执行语句listc＝sorted(lista，resverse＝True)后，列表listc中的元素为[36，28，23，22，19，17，12]，从而实现降序排序。
4.冒泡排序
(1)冒泡排序的基本思想
冒泡排序是在数列中对________两个数据依次进行________和位置调整，让较大的数“下沉(或上冒)”，较小的数据“上冒(或下沉)”的一种排序技术。
(2)冒泡排序的特点
①________两个数据进行比较。
②n个数据完成排序，共进行________趟(遍)排序。
③n个数据完成排序，数据的比较次数为。
④n个数据完成排序，其时间复杂度为________。
5.冒泡排序算法的程序实现
说明：对列表list1中的数据进行升序排序
def bubble_sort(list1)：
count＝len(list1)
#count个数排序共需进行count－1趟
for i in range(1，count)：
#每一趟排序从前往后进行，比较相邻两个数
for j in range(0，count－i)：
　　　　　　if list1[j]>list1[j＋1]：
　　　　　list1[j]，list1[j＋1]＝list1[j＋1]，list1[j]
return list1
(1)冒泡排序进行时，数据的比较可以由前往后进行，即list1[j]与listl[j＋1]比较；也可以由后往前进行，即list1[j]与list1[j－1]比较，此时应将循环条件“for j in range(0，count－i)：”修改为“for j in range(count－1，i－1，－1)：”。
(2)若要将数据按降序排列，只需将语句“if list1[j]>list1[j＋1]：”修改为“if list1[j]例1 采用冒泡排序算法对数据序列“21，15，23，26，33，18，46，17”完成升序排序，理论上讲共需进行排序的遍数为(　　)
A.3遍 B.4遍 C.7遍 D.8遍
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　采用冒泡排序算法对数据序列“16，11，8，9，21，32，28”完成升序排序，共进行数据交换的次数为(　　)
A.3次 B.4次 C.5次 D.6次
例2 采用冒泡排序算法对8个数据“48，65，29，16，22，75，36，41”进行降序排序，则第3遍的排序结果是(　　)
原始数据 48，65，29，16，22，75，36，41
第1遍完成后的数据为 75，48，65，29，16，22，41，36
第2遍完成后的数据为 75，65，48，41，29，16，22，36
第3遍完成后的数据为
A.75，65，48，41，36，29，16，22
B.75，65，48，41，29，16，22，36
C.75，65，48，41，36，29，22，16
D.75，65，48，41，29，22，16，36
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　小明对6个数字“3，5，8，2，6，1”进行两遍冒泡排序后的数字序列设置为办公室门的密码锁，则该密码可能是(　　)
①1 2 3 5 8 6　②8 6 3 5 2 1　③1 2 3 5 6 8
④3 2 5 1 6 8　⑤8 5 6 3 2 1
A.①②③④⑤ B.①② C.④⑤ D.①②④⑤
例3 列表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]的升序排列
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序段：
b＝[17，8，6，15，21，36，18，33]
n＝len(b)
for i in range(1，4)：
for j in range(n－1，i－1，－1)：
if b[j]>b[j－1]：
　　　b[j]，b[j－1]＝b[j－1]，b[j]
经过该程序段“加工”后，列表b中的元素为(　　)
A.[36，33，17，8，6，15，21，18]
B.[36，33，21，17，15，8，6，18]
C.[36，33，21，17，8，6，15，18]
D.[36，33，21，18，17，8，6，15]
例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]
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下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
1.采用冒泡排序算法对数据序列“9，7，6，8，5，4，2，3”进行升序排序，约定从前往后进行数据比较及位置交换，则第2趟排序结束时的数据序列为(　　)
A.7，6，8，5，4，2，3，9 B.6，7，5，4，2，3，8，9
C.6，5，4，2，3，7，8，9 D.6，7，4，2，3，5，8，9
2.采用冒泡排序算法对数据序列“6，8，9，5，4，2，7，3”进行降序排序，约定从后往前进行数据比较及位置交换，则进行第2趟排序时的数据交换次数为(　　)
A.0次 B.1次 C.2次 D.3次
3.有如下Python程序段：
b＝[99，88，77，66，55，61，71，81]
count＝len(b)
for i in range(1，4)：
for j in range(0，count－i)：
　　 　if b[j]>b[j＋1]：
　　　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
经过该程序段“加工”后，列表b中的元素为(　　)
A.[77，66，55，61，71，81，88，99]
B.[55，61，66，71，77，81，88，99]
C.[66，55，61，71，77，81，88，99]
D.[66，61，55，71，77，81，88，99]
4.有如下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
5.有如下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 key　 　　a[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]
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＝[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]
8.有如下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
9.有如下Python程序段：
a＝[3，8，6，2，1，0，7]
n＝len(a)
for i in range((n－1)∥2):
　j＝0；k＝1
　 while j　　 if a[j]*k>a[j＋2]*k:
　　　 a[j]，a[j＋2]＝a[j＋2]，a[j]
　　　j＝j＋1；k＝－k
执行该程序段，则a[4：7]的值为(　　)
A.6，0，7 B.6，7，8 C.3，8，1 D.6，8，7
课时3　数据排序
知识梳理
1.(1)无序　有序　(2)升序　降序
2.冒泡排序　选择排序
3.(1)直接　新的　(2)新的序列
4.(1)相邻　比较　(2)①相邻　②n－1　④O(n2)
5.0，count－i　list1[j]>list1[j＋1]
例题精析
例1　C　[共有8个数据，共需要进行7遍排序， 因此答案为C。]
变式训练　D　[本题主要考查的是冒泡排序思想。排序过程如下：
原始数据 16，11，8，9，21，32，28 交换次数
第1遍完成后的数据为 8，16，11，9，21，28，32 交换3次
第2遍完成后的数据为 8，9，16，11，21，28，32 交换2次
第3遍完成后的数据为 8，9，11，16，21，28，32 交换1次
第4遍完成后的数据为 8，9，11，16，21，28，32 不交换
… … 不交换
因此，完成升序排序，共交换的次数为6次，答案为D。]
例2　A　[本题主要考查的是冒泡排序的实现。根据第1、2遍可知，冒泡排序是从后往前进行降序排序，根据第2遍的结果可推出第3遍的排序结果为75，65，48，41，36，29，16，22，因此，答案为A。]
变式训练　D　[本题主要考查的是冒泡排序思想。排序方式有升序和降序，排序的方向可以从前往后或从后往前，因此要分4种情况进行讨论分析。如果是升序排序，从前往后进行两遍后数据序列为②，从后往前进行两遍后数据序列为①；如果是降序排序，从前往后进行两遍后数据序列为⑤，从后往前进行两遍后数据序列为④。因此，①②④⑤都有可能，答案为D。]
例3　A　[本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1，5]，条件s[j]>s[j－1]表示当后一个数大于前一个数时要发生交换，实现降序排列。参加排序元素仅s[0]～s[5]。]
变式训练　C　[本题主要考查的冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法进行降序排序3遍，数据比较是从后往前进行的，进行第1遍排序后的数据序列为[36，17，8，6，15，21，33，18]，进行第2遍排序后的数据序列为[36，33，17，8，6，15，21，18]，进行第3遍排序后的数据序列为[36，33，21，17，8，6，15，18]，因此答案为C。]
例4　D　[实现从后往前冒泡升序排列，前面的数据先有序，但右端没有固定，每趟都在缩减，因此有些数是排不到的。AB选项排序后均为5，6，9，8，无序，可以检测。C选项排序后为5，8，9，6，无序，可以检测。D选项排序为升序，与正确算法结果相同，无法检测。]
变式训练　C　[程序实现从后往前降序排序，q记录有序数据的个数，第1趟比较了5次，第2趟比较了3次，d的值为[12，10，8，8，6，3]，q的值为4，排序后，数据有序，第3趟只比较1次，数据无交换，结束排序，比较次数分别为5＋3＋1＝9。]
随堂检测
1.B　[第1趟排序结束时的数据序列为7，6，8，5，4，2，3，9，第2趟排序结束时的数据序列为6，7，5，4，2，3，8，9。 因此，答案为B。]
2.C　[第1趟排序结束时的数据序列为9，6，8，7，5，4，2，3，数据交换5次，第2趟排序结束时的数据序列为9，8，6，7，5，4，3，2，数据交换2次，因此答案为C。]
3.C　[本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法进行升序排序3遍，数据比较是从前往后进行的，第1遍排序后列表b中的元素为[88，77，66，55，61，71，81，99]，第2遍排序后的数据序列为[77，66，55，61，71，81，88，99]，第3遍排序后的数据序列为[66，55，61，71，77，81，88，99]，因此答案为C。]
4.A　[加框处语句表示交换次数，从条件s[j]5.B　[本题考查排序算法和随机数函数。首先列表a中的初始值是[1，10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a的合适位置上，使得列表a的值非降序排列，因此选项A、C、D都是有可能的。]
6.C　[本题考查索引排序。数组a存储的0－5的索引位置，程序实现从前往后冒泡，当条件s[a[j]]>s[a[j＋1]]成立时交换，实现升序排列，因此排序后的结果是abbccc，找到这些字母的索引位置。]
7.A　[从后往前冒泡，排了3趟。]
8.C　[外循环控制排序的次数，也与排序的区间位置有关。冒泡排序必须是一端固定，另一端随着排序的过程将不断地缩短。若从前往后冒泡，则排序的初值必须为a，第一趟排序的区间是最长的，此时i的值为0，最后位置为b，而j＋1到过b时，j的值为b－1，若要取到b－1，则终值必须为b，结合i的值，终值为b－i。]
9.A　[当k为1时，a[j]>a[j＋2]表示升序排序，k为－1时，降序排序；程序实现奇位升序，偶位降序排列。

展开更多......

收起↑