iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
自我挑戰組

30天不怕演算法:白話文版系列 第 7

Day 07:泡沫排序(bubble sort)

如果一個陣列中的任兩個元素是有排序的,是不是代表整個陣列就是排序好的?
這就是泡沫排序的想法。

如果我們想將一列數字由小到大排好,用泡沫排序的步驟是:

  1. 兩個相鄰的數字相比,如果第二個比第一個小,兩個數字交換。
  2. 從頭到尾任兩個數字都進行同樣操作,最後一個數字排序完成。
  3. 除了最後一個數字外,再從頭開始進行相鄰數字比較。
  4. 重複上述步驟直到所有數字都排序好。

舉例來說:
3, 6, 2, 7, 1, 4, 5
// 首先3, 6相比,不交換

3, 6, 2, 7, 1, 4, 5
// 6, 2相比,交換

3, 2, 6, 7, 1, 4, 5
// 6, 7 相比,不交換

3, 2, 6, 7, 1, 4, 5
// 7, 1 相比,交換

3, 2, 6, 1, 7, 4, 5
// 7, 4 相比,交換

3, 2, 6, 1, 4, 7, 5
// 7, 5 相比,交換

3, 2, 6, 1, 4, 5, 7
// 一輪比完後,最大的數字7會換到最後一個位置

可以看到在比較的過程,最大的數字碰到任何數字都會被往後交換,視覺上就像泡泡一樣浮到陣列的最末尾,所以才有泡沫排序這個名稱。如此一來,最後一個數字就算排序完成,所以下一輪的比較就不需要再操作最後一個數字。

泡沫排序跟選擇排序一樣,一次排好一個數字,每一輪要經過逐一比較才完成,所以它的執行時間一樣也是O(n²)。

正常來說,泡沫排序在最佳情況也會把所有元素比較一遍,不過如果是操作有序陣列,過程中不會有任何元素交換,所以我們可以增加一個條件,「如果沒有任何元素交換,排序結束」,這樣可以讓泡沫排序比較一遍就結束,等於最佳情況執行時間可以降到Ω(n)。

泡沫排序還有其他的變形,例如雞尾酒排序(cocktail shaker sort)。雞尾酒排序的特點是排序是雙向的,也就是會從第一個元素開始比較相鄰元素、排好末尾的數字,再從陣列末尾比較回來、排好第一個數字。以下是雞尾酒排序的示意圖:

圖片來源:維基百科

雖然這樣的雙向排序好像增進了一點點效能,它的平均執行時間仍然要O(n²)。整體來說,泡沫排序和雞尾酒排序等變化型仍然都算是非常慢的演算法。

接下來會寫到一些手法不同、效率更高的演算法。


上一篇
Day 06:選擇排序(selection sort)
下一篇
Day 08:分治法與遞迴(1)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言