Contents
  1. 1. 概念
  2. 2. 時間複雜度
  3. 3. 空間複雜度
  4. 4. 穩定性
  5. 5. Code

概念

走訪要排序的數列,一一比較兩個相鄰元素,如果它們的”順序應該相反”就會做交換,會一直重複走訪數列直到沒有再做任何交換為止。

何謂”順序應該相反”?
例如:數列 1 3 2
1小於3所以順序正確,但是3大於2,3應該要在2後面,所以3和2會交換,變成 1 2 3

這邊以”由數列前端走訪到後端”來做例子,由於是往數列後端移動,所以走訪過程中,數列中的最大值會一直被兩兩交換,移到最右邊(該數已經被排序好),所以在下次遍歷時,可以把遍歷範圍往左縮小一個單位(減1),只遍歷還沒排序好的部分(如以下動畫)。


(File from Bubble sort wiki, CC BY-SA 3.0)

依據此概念,我們可以得知第一次遍歷數列時,會先找出整個數列中最大值放在最右邊,第二次遍歷時,會找出整個數列中第二大的數值放在最大值往左一個單位,第三次遍歷時,會找出整個數列中第三大的數值放在第二大的數值往左一個單位…依此概念一直重複n次,就會完成排序了。但是此方法會需要O(n2)的比較次數,如果使用一個旗標來表示該次遍歷有無交換數值,可以在該數列已經排序好時提前結束演算法,此方法可以讓演算法最好的複雜度降低到O(n)。而Bubble sort只有在排序的元素非常少的時候,才有不錯的效率,其餘都很差。

時間複雜度

Best : O(n)
Average : O(n2)
Worst : O(n2)

空間複雜度

O(1)

穩定性

穩定

Code

See my code on github.

參考資料:
Bubble sort wiki
Sorting algorithm wiki