氣泡排序是資料結構中的經典演算法,手動實現氣泡排序,對初學者鍛鍊自己的程式設計邏輯有很大幫助,本節就帶領大家使用迴圈結構實現氣泡排序演算法。
氣泡排序演算法的實現思想遵循以下幾步:
-
比較相鄰的元素,如果第一個比第二個大,就交換它們兩個。
-
從最開始的第一對到結尾的最後一對,對每一對相鄰元素做步驟 1 所描述的比較工作,並將最大的元素放在後面。這樣,當從最開始的第一對到結尾的最後一對都執行完後,整個序列中的最後一個元素便是最大的數。
-
將迴圈縮短,除去最後一個數(因為最後一個已經是最大的了),再重複步驟 2 的操作,得到倒數第二大的數。
-
持續做步驟 3 的操作,每次將迴圈縮短一位,並得到本次迴圈中的最大數。直到回圈個數縮短為 1,即沒有任何一對數位需要比較,此時便得到了一個從小到大排序的序列。
通過分析氣泡排序演算法的實現原理,要想實現該演算法,需要藉助迴圈結構,更確切地說,需要使用巢狀迴圈結構,使用 for 迴圈或者 while 迴圈都可以。
例如,使用 for 迴圈實現用氣泡排序演算法對 [5,8,4,1] 進行排序:
data = [5,8,4,1]
#實現氣泡排序
for i in range(len(data)-1):
for j in range(len(data)-i-1):
if(data[j]>data[j+1]):
data[j],data[j+1] = data[j+1],data[j]
print("排序後:",data)
執行結果為:
排序後: [1, 4, 5, 8]
可以看到,實現氣泡排序使用了 2 層迴圈,其中外層迴圈負責氣泡排序進行的次數,而內層迴圈負責將列表中相鄰的兩個元素進行比較,並調整順序,即將較小的放在前面,較大的放在後面。