冒泡排序算法任務(wù)單
說在前面
冒泡排序是經(jīng)典排序算法之一，它通過對相鄰兩個元素依次進(jìn)行比較和調(diào)整，讓較大的元素“下沉”，較小的元素“上浮”來實現(xiàn)排序功能。冒泡排序的原理比較簡單，一般經(jīng)過教師的演示以后，學(xué)生都能根據(jù)指定的排序要求和掃描方向，寫出每趟排序的過程。
難點在于算法的代碼實現(xiàn)。冒泡排序的核心代碼是一個二重循環(huán)，其中內(nèi)層循環(huán)描述了每輪排序的過程，根據(jù)掃描范圍或方向的不同組合，可以產(chǎn)生各種不同的代碼實現(xiàn)。如果學(xué)生不理解變量的含義，只會死記硬背的話，就容易產(chǎn)生張冠李戴的錯誤。如何讓學(xué)生在紛繁復(fù)雜的變例拓展中抓住算法本質(zhì)，是一個亟需解決的教學(xué)難題。
正確理解代碼的關(guān)鍵在于明確變量的含義。運行一段程序就好比講述一個故事，每個代碼段都對應(yīng)一個故事情節(jié)，關(guān)鍵變量就是故事中的主人公。變量的含義不同，其所在代碼段的功能也就不一樣。具體到冒泡排序算法，其核心代碼是一個二重循環(huán)，賦予外層循環(huán)變量i不同的含義，我們就可以從不同的角度敘述冒泡排序的故事。
任務(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）仔細(xì)觀察排序過程，我們可以發(fā)現(xiàn)第3趟冒泡后數(shù)組已經(jīng)有序，后面4趟排序?qū)嶋H上沒有做任何交換操作。當(dāng)數(shù)組已經(jīng)有序時，能否提前結(jié)束排序，不再做無必要的掃描？我們可以設(shè)置一個標(biāo)記變量flag來標(biāo)記某趟排序過程中是否發(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è)置交互操作標(biāo)志
if 填空3: #無交換操作，表示已完成排序，退出循環(huán)
break
（2）當(dāng)采用向右掃描方式將最大值“冒泡”到右端時，經(jīng)典的代碼實現(xiàn)是設(shè)置二重for循環(huán)，其中外層循環(huán)變量i記錄排序趟數(shù)，內(nèi)層循環(huán)變量j記錄當(dāng)前元素的下標(biāo)。
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趟。
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è)置左邊界，分別都可以快速縮小掃描范圍。那么能否更進(jìn)一步，在內(nèi)層循環(huán)中向左、向右各掃描一次，分別設(shè)置左、右邊界呢？
當(dāng)然可以。這種算法被稱為雙向冒泡排序，又稱雞尾酒排序，每輪掃描下來可以更新左、右邊界，快速減少掃描范圍，提高了程序效率。
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
冒泡排序算法采用雙重for循環(huán)嵌套來實現(xiàn)，外層循環(huán)用來控制排序輪次（或待排序區(qū)間左邊界），內(nèi)層循環(huán)通過交換相鄰元素的方式，將較小值向左側(cè)冒泡。在每一輪排序結(jié)束后，都要把最小值冒泡到待排序區(qū)間最左端。
冒泡排序的比較次數(shù)與待排序元素的初始狀態(tài)無關(guān)，共需要進(jìn)行的比較次數(shù)是(n–1)+(n–2) + … +2+1 = n*(n–1)/2 。
冒泡排序的交換次數(shù)與待排序元素的初始狀態(tài)有關(guān)，序列中逆序?qū)Φ臄?shù)量就等于排序過程中的交換次數(shù)。
可以使用設(shè)置交換操作標(biāo)記、快速縮小右邊界和雙向冒泡排序等優(yōu)化方法來提高冒泡排序的效率。
需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來！
相關(guān)優(yōu)秀文章：