泡泡排序 (Bubble Sort)

程式資結演算法

Written by:

由左而右、兩兩比較相鄰資料,若前者大於後者,則將兩者交換來完成排序。當資料個數為 n 時,比較過程將分成 n-1 回合。

第 i 回合會將第 i 大的資料像泡泡一樣浮現在由右數回來的第 i 個位置。

比如 A[4] = {2, 4, 7, 3},第 1 回合要把第 1 大的數字 7 排序:

如果某回合過程中完全沒有發生交換,則代表排序完成,後面回合也無須再進行。

虛擬碼

 

程式碼

 

時間複雜度

1. Best Case: O(n)

input data 恰好由小到大呈現

 

2. Worst Case: O(n2)

input data 反序由大到小呈現。

改用 Recursive Time Function 來解:

 

3. Average Case: O(n2)

 

空間複雜度: O(1)

需要一個額外的空間儲存 temp 變數來做交換。

 

穩定性: Stable

由於 5 並不大於 5*,交換不發生、仍維持原順序,故為 Stable Sorting。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *