說在前面

【資料圖】

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

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

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

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

任務(wù)2. 冒泡排序優(yōu)化。

經(jīng)典的冒泡排序算法，對長度為n的數(shù)組需要排序n-1趟。

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

第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）仔細觀察排序過程，我們可以發(fā)現(xiàn)第3趟冒泡后數(shù)組已經(jīng)有序，后面4趟排序?qū)嶋H上沒有做任何交換操作。當數(shù)組已經(jīng)有序時，能否提前結(jié)束排序，不再做無必要的掃描？我們可以設(shè)置一個標記變量flag來標記某趟排序過程中是否發(fā)生了交換操作，若無交換操作，表示已完成排序，退出循環(huán)。

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

def bubble_sort_3(a):

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

swapFlag = False #先假設(shè)未做交換操作

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

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

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

swapFlag = 填空2 #設(shè)置交互操作標志

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

break

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

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

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

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

def bubble_sort_5(a):

right = len(a)-1

while 填空1:

swapPos = 0 #先假設(shè)最后一次發(fā)生交換操作的位置為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 #記錄發(fā)生交換操作的位置

right = 填空3

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

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

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

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

def bubble_sort_7(a):

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

while 填空1:

swapPos = left #先假設(shè)最后一次發(fā)生交換操作的位置為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

總結(jié):

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

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

冒泡排序的交換次數(shù)與待排序元素的初始狀態(tài)有關(guān)，序列中逆序?qū)Φ臄?shù)量就等于排序過程中的交換次數(shù)。

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

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

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

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類

關(guān)鍵詞： 冒泡排序 掃描方式 掃描范圍