冒泡排序算法任務(wù)單|新視野
說在前面
【資料圖】
冒泡排序是經(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)閱讀
-
冒泡排序算法任務(wù)單|新視野
說在前面冒泡排序是經(jīng)典排序算法之一,它通過對相鄰兩個元素依次進... -
每日快訊!“奧運排行榜”教學思路
說在前面“奧運排行榜”是一個源于實際的排序問題,每個國家的信息... -
2022年“防疫賬本”批露,這一年,防疫...
近日,全國各省市陸續(xù)公布了2022年衛(wèi)生費用相關(guān)的統(tǒng)計數(shù)據(jù)。有22個... -
YOLOv8官方支持多目標跟蹤 | ByteTrac...
點擊下方卡片,關(guān)注「集智書童」公眾號點擊加入「集智書童-YOLO算法... -
老胡已瘋,他說公務(wù)員加班太辛苦|全球球...
拿什么來形容一下胡錫進呢?不太好說,他似乎陷入了某種混沌不清的... -
推薦十個優(yōu)秀的富文本編輯器 今日看點
前言富文本編輯器是一種可嵌入瀏覽器網(wǎng)頁中,所見即所得的文本編輯...