冒泡排序算法任務單|新視野

說在前面

【資料圖】

冒泡排序是經典排序算法之一，它通過對相鄰兩個元素依次進行比較和調整，讓較大的元素“下沉”，較小的元素“上浮”來實現排序功能。冒泡排序的原理比較簡單，一般經過教師的演示以后，學生都能根據指定的排序要求和掃描方向，寫出每趟排序的過程。

難點在于算法的代碼實現。冒泡排序的核心代碼是一個二重循環，其中內層循環描述了每輪排序的過程，根據掃描范圍或方向的不同組合，可以產生各種不同的代碼實現。如果學生不理解變量的含義，只會死記硬背的話，就容易產生張冠李戴的錯誤。如何讓學生在紛繁復雜的變例拓展中抓住算法本質，是一個亟需解決的教學難題。

正確理解代碼的關鍵在于明確變量的含義。運行一段程序就好比講述一個故事，每個代碼段都對應一個故事情節，關鍵變量就是故事中的主人公。變量的含義不同，其所在代碼段的功能也就不一樣。具體到冒泡排序算法，其核心代碼是一個二重循環，賦予外層循環變量i不同的含義，我們就可以從不同的角度敘述冒泡排序的故事。

冒泡排序算法任務單（學生版）：任務1. 經典冒泡排序算法。已知數組d的初始值為[3, 2, 5, 4, 6, 1]，采用冒泡排序算法對其進行從小到大排序。（1）若采用向右掃描方式將最大值“冒泡”到右端，請寫出每一趟排序后數組d的值。（2）若采用向左掃描方式將最小值“冒泡”到左端，請寫出每一趟排序后數組d的值。（3）若采用向右掃描方式將最大值“冒泡”到右端，已知數組d的長度為n，請問總共需要排序多少趟？每趟比較次數分別為多少？總共比較次數為多少？（4）教材p131給出了采用向右掃描方式將最大值“冒泡”到右端的算法流程圖和代碼實現。但是由于排版的原因，代碼實現與流程圖并不完全一致（變量名稱不同），請修改代碼，使其與流程圖保持一致，分別用for循環和while循環語句來實現程序功能。（5）若采用向左掃描方式將最小值“冒泡”到左端，請分別用for循環和while循環語句實現程序功能。體會將最小元素“上浮”和最大元素“下沉”兩種方式在程序實現中的區別。

任務2. 冒泡排序優化。

經典的冒泡排序算法，對長度為n的數組需要排序n-1趟。

例如，對數組a=[5,1,3,4,2,6,7,8],需要向右掃描排序7趟，每趟排序結果如下：

第1趟：[1,3,4,2,5,6,7,8]

第2趟：[1,3,2,4,5,6,7,8]

第3趟：[1,2,3,4,5,6,7,8]

第4趟：[1,2,3,4,5,6,7,8]

第5趟：[1,2,3,4,5,6,7,8]

第6趟：[1,2,3,4,5,6,7,8]

第7趟：[1,2,3,4,5,6,7,8]

（1）仔細觀察排序過程，我們可以發現第3趟冒泡后數組已經有序，后面4趟排序實際上沒有做任何交換操作。當數組已經有序時，能否提前結束排序，不再做無必要的掃描？我們可以設置一個標記變量flag來標記某趟排序過程中是否發生了交換操作，若無交換操作，表示已完成排序，退出循環。

參考代碼如下，請將缺失的代碼補充完整。

def bubble_sort_3(a):

for i in range(1, len(a)):

swapFlag = False #先假設未做交換操作

for j in range(len(a)-i):

if a[j] > a[j+1]:

a[j], a[j+1] = 填空1

swapFlag = 填空2 #設置交互操作標志

if 填空3: #無交換操作，表示已完成排序，退出循環

break

（2）當采用向右掃描方式將最大值“冒泡”到右端時，經典的代碼實現是設置二重for循環，其中外層循環變量i記錄排序趟數，內層循環變量j記錄當前元素的下標。

其實我們也可以從另一個角度來理解冒泡排序算法：假設當前數組中待排序序列為a[0:r+1]，其中r是序列的右邊界；每趟排序都是從最左端開始向右掃描待排序區域，將最大值“冒泡”到a[r]處；r的初始值為len(a)-1，每完成一趟排序，就令r=r-1；當r=0時，待排序序列中只有一個元素，排序結束。參考代碼如下，請將缺失的代碼補充完整。

def bubble_sort_4(a):

for r in range(len(a)-1, 0, -1):

for j in range(填空1):#向右掃描，將最大值冒泡到a[r]

if 填空2 :

a[j], a[j+1] = a[j+1], a[j]

（3）使用函數bubble_sort_4(a)對數組a=[5,1,3,4,2,6,7,8]排序，每趟排序只讓右邊界r左移1位，總共需要排7趟。

觀察排序過程，分析第一趟排序時，哪些元素的位置沒有變化？最后一次交換操作發生在哪兩個元素之間？。一般情況下，每排序一趟就將右邊界r左移一位，能否在某趟排序之后，直接將右邊界移動到正確位置，以快速縮小下一趟排序的掃描范圍？我們可以設計一個冒泡排序的優化算法，通過記錄最后一次發生交換操作的位置，把它作為下一趟排序的右邊界，實現快速縮減掃描范圍的目的。參考代碼如下，請將缺失的代碼補充完整。

def bubble_sort_5(a):

right = len(a)-1

while 填空1:

swapPos = 0 #先假設最后一次發生交換操作的位置為0

for j in range(right): #順序掃描a[0:right]

if a[j] > a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

swapPos = 填空2 #記錄發生交換操作的位置

right = 填空3

（4）向右掃描時，可以設置右邊界，通過更新右邊界，實現快速縮減掃描范圍的目的。那么，能否在向左掃描時，通過快速更新左邊界來提高程序效率呢？請模仿函數bubble_sort_5(a)，編寫向左掃描數組將最小值“冒泡”到左端的冒泡排序優化算法。

（5）既然向右掃描時可以設置右邊界，向左掃描時可以設置左邊界，分別都可以快速縮小掃描范圍。那么能否更進一步，在內層循環中向左、向右各掃描一次，分別設置左、右邊界呢？

當然可以。這種算法被稱為雙向冒泡排序，又稱雞尾酒排序，每輪掃描下來可以更新左、右邊界，快速減少掃描范圍，提高了程序效率。

參考代碼如下，請將缺失的代碼補充完整。

def bubble_sort_7(a):

left, right = 0, len(a)-1

while 填空1:

swapPos = left #先假設最后一次發生交換操作的位置為left

for j in range(left,right): #順序掃描a[left:right]

if a[j] > a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

swapPos =填空2

right =填空3

for j in range(right,left,-1): #逆序掃描a[left+1:right+1]

if a[j] < a[j-1]:

a[j],a[j-1] = a[j-1],a[j]

swapPos =填空4

left =填空5

總結:

冒泡排序算法采用雙重for循環嵌套來實現，外層循環用來控制排序輪次（或待排序區間左邊界），內層循環通過交換相鄰元素的方式，將較小值向左側冒泡。在每一輪排序結束后，都要把最小值冒泡到待排序區間最左端。

冒泡排序的比較次數與待排序元素的初始狀態無關，共需要進行的比較次數是(n–1)+(n–2) + … +2+1 = n*(n–1)/2 。

冒泡排序的交換次數與待排序元素的初始狀態有關，序列中逆序對的數量就等于排序過程中的交換次數。

可以使用設置交換操作標記、快速縮小右邊界和雙向冒泡排序等優化方法來提高冒泡排序的效率。

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關優秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類

關鍵詞： 冒泡排序 掃描方式 掃描范圍