資源簡介

專題17　排序算法
學業要求 知　識　點 學業水平等級
1.從相鄰數據比較和交換的本質理解冒泡排序的算法思想 4
2.通過對內、外循環和比較語句的功能，用程序代碼實現冒泡排序 4
知識點一　冒泡排序算法思想
【知識梳理】
1.________(sorting)是使系列中的元素按照某個字段的值遞增(或遞減)的次序重新排列的操作。在排序的過程中，元素的值保持不變，但其在系列中的順序可能會改變。
2.待排序的數據存儲方式一般有________和鏈表兩種方式，利用數組存儲數據，在排序時需要對數據本身進行物理重排，可能需要移動數據的位置，而利用鏈表存儲數據，只需要修改指針即可。
3.常見的排序算法有________排序、選擇排序、插入排序、快速排序、堆排序、歸并排序、桶排序等。在選擇排序的算法時，可以根據待排序數據自身的特點來選擇相應的算法。
4.冒泡排序(Bubble__Sort)是在一系列數據中對________兩個數依次進行比較和調整，讓較大的數“下沉(上冒)”，較小的數“上冒(下沉)”的一種排序技術。
5.冒泡排序算法把待排序的n個元素的數組看成是垂直堆放的一列數據，對相鄰兩個數據進行比較，將較________的數據換到上面的一個元素中(升序)。重復這一過程，直到處理完最后兩個元素中的數據，稱為一遍加工。當第一遍加工完成時，最小的數據已經“上浮”到第一個元素的位置(升序)。然后對余下的n－1個元素重復上述處理過程，直達最后進行余下兩個數據的比較和交換。
6.對于n個元素的數組，共需要________遍加工，第一遍加工的比較次數為________次，第二遍加工的比較次數為n－2次，以此類推，最后一遍加工的比較只需________次。所以用冒泡排序算法進行排序時，共需比較n(n－1)/2(次)。其時間復雜度為________。
【經典案例】
冒泡排序特征是對相鄰兩個數依次進行比較和交換，外循環決定了排序的趟數和有序數據的位置，內循環決定了排序的方向和排序區間，比較語句決定升降序方式。排序往往先找出一列數中的最值，將這個最值交換到該列數的末端，把數列劃分為有序區間和無序區間，把這個操作稱為一趟排序。再對無序區間進行重復操作，不斷地擴大有序區間，縮小無序區間，當無序區間中只有一個數據時，全部數據有序，結束排序。排序基本算法思想是迭代執行一趟排序，直到數據全部有序，因此描述并畫出第i趟排序的算法，讓學生能看得見排序的過程，是理解排序算法本質思想的關鍵。
【例1】 采用冒泡排序算法對某數據進行降序排列，經過第一輪排序后的結果是“2，3，4，1，5，0”，那么原數據序列不可能的是(　　)
A.2，3，0，4，5，1 B.0，2，3，4，1，5
C.1，2，3，4，0，5 D.2，0，3，4，1，5
思維點撥
明考向 本題考查冒泡排序的算法思想。從第一輪排序后的結果來看，0是最小值，最值出現的位置在后面，因此屬于從前往后的降序排列
精點撥 A 一輪后應為2，3，4，5，1，0，與題目要求不符
B 從前往后將0推到最后
C 1依次和2，3，4交換，0和5交換
D 0依次為3，4，1，5交換
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 采用冒泡排序算法對某數據序列進行排序，第一輪排序后的結果是“2，8，6，3，5，7，9”，則第二輪排序需要交換的次數為(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
【例2】 某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.每一遍加工中，最小的元素“上浮”
思維點撥
明考向 本題考查排序算法
精點撥 A 當條件s[j]B 應為升序排列，而不是降序排列
C 若s已經有序，程序沒有作優化，還是要比較，但不交換，因此時間復雜度為O2
D 排序過程中小的數據往前移動，形象地看成是上浮
聽課筆記：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 列表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.排序比較對象若為a[j]和a[j＋2]，則實現奇偶位________排序。
2.當排序的條件有兩個或多個時，或者出現了多分支的選擇結構，實現的________排序。
3.若每趟交換的次數為0，表示所有數據均________序，可以提前結束排序算法。也可以記flag的狀態為False，若發生交換，將flag的值修改為True，根據flag的值，也可以表示數據是否有序。
4.從后往前冒泡的每趟排序實現了[0，i]之間的數據有序，因此下趟排序的區間為[________，n－1]。記錄第i趟排序最后一次交換(a[j]和a[j－1]比較)后的有序位置j－1，此時表示[0，j－1]已經有序，下趟排序的區間可以修改為[j，n]，縮小下趟排序的區間，減少排序的次數，達到優化排序的效果。
5.從前往后冒泡的每趟排序實現了[n－i，n－1]之間的數據有序，因此下趟排序的區間為[0，________]。記錄第i趟排序最后一次交換(a[j]和a[j＋1]比較)后的有序位置j＋1，此時表示[j＋1，n]已經有序，下趟排序的區間可以修改為[0，j]，縮小下趟排序的區間，減少排序的次數，達到優化排序的效果。
【經典案例】
在排序過程中，若不要求全部數據有序，而是挑出前n個數據，可以設置條件，提前結束排序。若排序的對象分組依次存儲，可以在內循環中設置步長，起到分組排序的目的。還可以在比較語句中設置多個比較條件，實現多關鍵字的排序。甚至用while循環來表達外循環，根據每趟排序的有序區間，設置外循環i的終值，縮小下趟排序的區間，減少排序的次數。
【例1】 有如下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
思維點撥
明考向 本題考查冒泡排序的算法思想
精點撥 提前結束排序的條件必須滿足兩個，其一大于等于m，其二是最后的數據與前面的數據不能相等。如要排出前3名，且有很多并列第3名(排好序[1，3，3，3，4，6，7]，需要找到4即最后一個不符合條件的數據，才能終止循環
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 數組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]，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]降序，偶位元素升序排列
【例2】 有實現冒泡排序的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
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 列表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.①③⑥
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.采用冒泡排序對數據序列“15 89 60 34 10 28 70”完成升序排序，在排序過程中，數據“60”發生交換的次數分別可能為(　　)
A.2 B.3
C.4 D.5
3.采用冒泡排序算法，對某數組數據進行排序，經過一輪后的結果是“2，3，9，5，6，7”，那么下列說法不正確的是(　　)
A.這輪排序，有可能沒發生數據交換
B.這輪排序，有可能只發生了1次數據交換
C.排序結束后，數據是升序的
D.完成全部排序后，數據交換的次數和冒泡的方向無關
4.采用冒泡排序算法對數據序列“8，3，5，2，0，9”進行排序，第一輪排序后的結果為“0，8，3，5，2，9”，則整個序列完成排序的交換次數是(　　)
A.6次 B.7次
C.8次 D.9次
5.采用冒泡排序算法對數據序列“7，3，8，2，1，9”進行排序，第一輪排序后的結果為“3，7，2，1，8，9”，則完成整個排序需要交換的次數是(　　)
A.6次 B.7次
C.8次 D.9次
6.如下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']
7.使用列表a和列表b分別存儲學生的總分和考號，已知考號為b[i]的學生的總分為a[i]，使用Python編程實現如下功能：將成績數據“按總分降序排序、總分相同按學號升序排序”，代碼如下。
n＝len(a)
for i in range(1，n)：
for j in range(0，n－i)：
　 if or and ：
　 　　　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＋1]則(1)(2)(3)處代碼依次為(　　)
A.③②④ B.①⑤⑥
C.③②⑥ D.①⑤④
8.列表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]的降序排列
專題17　排序算法
知識點一
知識梳理
1.排序　2.數組　3.冒泡　4.相鄰　5.小 6.n－1　n－1　1　O(n2)
經典案例
例1　A
變式1　A　[本題考查冒泡排序算法的相關知識。由第一輪數據“2，8，6，3，5，7，9”可知，采用冒泡排序對數據進行升序排序，但有兩種可能，一種是從后往前的冒泡升序，則第二輪排序后的數據為“2，3，8，6，5，7，9”，交換2次，另一種是從前往后的冒泡升序，則第二輪排序后的數據為“2，6，3，5，7，8，9”，交換4次。]
例2　D
變式2　A　[本題考查冒泡排序算法思想。外循環變量i控制排序趟數。內循環變量j取值范圍是[1，5]，條件s[j]>s[j－1]表示當后一個數大于前一個數時要發生交換，實現降序排列。參加排序元素僅s[0]～s[5]。]
知識點二
知識梳理
1.分組　2.多關鍵字　3.有　4.i＋1　5.n－i－1
經典案例
例1　C
變式1　A　[本題考查冒泡排序的算法思想。內循環j，初值為n－2＝8，步長為－2，因此j的值為8至2的偶數。比較對象也是這些位置中的數，因此僅實現這些數的升序排列。]
例2　D
變式2　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]”。]
當堂過關檢測
1.D　[A、B選項符合從后往前比較，將最小數交換到最前面，C選項符合從前往后比較，將最大的數交換到最右邊。而D選項不管從哪個方向進行依次比較，都不符合。]
2.C　[本題主要考查選擇排序和冒泡排序的算法思想。冒泡排序中第一趟排序結果為10，15，89，60，34，28，70，60被交換1次，第二趟排序結果為10，15，28，89，60，34，70，60被交換1次，第三趟排序結果為10，15，28，34，89，60，70，60被交換1次，第四趟排序結果為10，15，28，34，60，89，70，60被交換1次，此后的交換與60無關，60共被交換4次。]
3.A　[本題考查冒泡排序。經過一輪后最小數在最前面，可知，該冒泡排序是從后往前冒泡，升序。A選項原始數據最小數2不在最前面，一定會發生交換。若原始數據就是一趟排序結果，9在中間，無論是從后往前，還是從前往后，都要發生數據交換。B選項若原始數據如果為“2，3，5，9，6，7”，那么就發生了一次交換。C選項從一趟結果來看，是升序排列。D選項數據的交換取決于逆序對的個數，與排序方向無關。]
4.D　[本題考查冒泡排序算法思想。數據序列最大值和最小值分別為9和0，若實現從后往前升序排列，符合題目描述。若實現從前往后升序，結果應為“3，5，2，0，8，9”。無論排序的方向如何，只要是實現升序，8換到相應位置需交換4次，3和5換到相應位置各需交換2次，2換到相應位置，需交換1次。]
5.C　[本題考查冒泡排序的算法思想。從第一輪排序后的結果來看，實現從前往后升序排列，只要找出序列中的逆序對，就可以判斷交換次數。7和后面的3，2，1是逆序對，3和2，1是逆序對，8和2，1是逆序對，2和1是逆序對，共有8組逆序對。]
6.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']。]
7.C　[本題考查冒泡排序。從for j in range(0，n－i)可知，從前向后冒泡，相鄰兩數兩兩比較；比較規則如下：第j個比j＋1個成績小則交換③，第j個和第j＋1個成績相同②且第j個考號比第j＋1個大⑥。]
8.C　[本題考查冒泡排序算法思想。從后往前冒泡，前面的數據先有序，有序區間的左端點是i＋1，比較對象是s[j]

展開更多......

收起↑