資源簡介

專題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]

展開更多......

收起↑