資源簡介

(共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?、? 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]?、踑[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)
答案?、賜＝len(nums)?、趀x_flag＝False ③k＝j
解析　本題主要考查冒泡排序算法的優化。題目中實現優化的方法是，當某趟排序過程中沒有發生數據的交換時，說明數據已經有序，結束數據的排序；同時，通過記錄最后發生數據交換的位置，縮小數據排序的范圍?？闸偬巒＝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)?、赼[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?。?：”模塊內，題中所給的樣例數據運行結果__________(是/否)受到影響，將樣例“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?。?來看，b[i][1]存儲的是各區域的訂單數量，數據庫中讀取各訂單所在區域，需先將a數組中A－H轉換成0－7的索引號，再對b數組進行累加計數。②計算所需派送人員。從語句k＝s－psryn來看，s是所需派送人員人數之和，每個區域產生尾單后，所需派送人員增加1人，因此先計算整數倍的值。③找到去除派單人員的條件。k是需去除派單人員，按尾單人數采用冒泡降序排序，找出符合條件最大的k個值，優先刪除派單尾數最少的區域中的派送人員，如果派單尾數相同，則在分配到派送人員數最多的區域中去掉一個派單人員，因此是一個雙關鍵字排序算法。(3)樣題給出數據的尾單數均不為0，因此條件b[i][1]%rs?。?始終成立，是否縮進不影響結果，只有當尾單出現為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?、趎um－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?、? 6 3 5 2 1?、? 2 3 5 6 8
④3 2 5 1 6 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):
?。?br/>　　　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?、躉(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時，降序排序；程序實現奇位升序，偶位降序排列。

展開更多......

收起↑