交換排序—冒泡排序(Bubble Sort)

交換排序主要是透過兩兩比較待排記錄的關鍵碼，若發生與排序要求相逆，則交換之。先來看看排序列一趟冒泡的過程：設1
泡方法為：

i=1； //設定從第一個記錄開始進行兩兩比較

若i≥j，一趟冒泡結束。

比較r[i].key 與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉⑤

當r[i].key >r[i+1].key 時， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]；將r[i]與r[i+1]交換

i=i+1；調整對下兩個記錄進行兩兩比較，轉②

交換排序—交換排序—冒泡排序(Bubble Sort)(Bubble Sort)方法：對n 個記錄的表，第一趟冒泡得到一個關鍵碼最大的記錄r[n]，第二個冒泡對n-1 個記錄的表，再得到一個關鍵碼最大的記錄r[n-1]，如此重複，直到n 個記錄按關鍵碼有序的表。

【演算法10.6】

j=n； //從n 記錄的表格開始

若j

i=1； //一趟冒泡，設定從第一筆記錄開始進行兩兩比較，

若i≥j，一趟冒泡結束，j=j-1；冒泡表的記錄數-1，轉②

比較r[i].key 與r[i+1 ].key，若r[i].key≤r[i+1].key，不交換，轉⑤

當r[i].key>r[i+1].key 時， r[i] r[i+1]； 將r[i]與r[i+1]交換

i=i+1；調整對下兩個記錄兩兩比較，轉④

【效率分析】
空間效率：僅使用了一個輔助單元。

時間效率：總共要進行n-1 趟冒泡，對j 個記錄的表進行一趟冒泡需要j-1 次關鍵碼比較。

移動次數：

最好情況下：待排序列已有序，不需移動

最壞情況下：每次比較後均要進行三次移動，

更多交換排序—交換排序—交換排序—冒泡排序(Bubble Sort)(Bubble Sort)(Bubble Sort)相關文章請關注PHP中文網！