iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
自我挑戰組

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

Day 06:選擇排序(selection sort)

先前看到了常見執行時間的圖形,線條越平代表演算法速度越快,越陡則代表越慢。

我們會發現O(log n)的二分搜尋其實算是數一數二快速的演算法,不過二分搜尋的條件是只能在有序陣列中施行,這也代表陣列是否有排序有時相當重要,所以也有許多的演算法在解決排序(sorting)的問題。

如果今天有七張蓋起來的撲克牌,隨意放在桌上,一次只能打開一張檢查。要怎麼樣讓這些牌由小到大排好呢?

最直接的方法,可能就是一張一張找出最小的牌。我們打開最左邊第一張,接著依序打開後面的牌跟它比較,如果發現比較小的牌,就交換位置,把較小的牌換到第一張,接這用這張牌繼續比較,如下面的例子:

3, 6, 2, 7, 1, 4, 5
// 打開第一張,3即是目前最小的牌。以3依序跟後面的數字比,比到2時發現2較小,把2換到第一個。

2, 6, 3, 7, 1, 4, 5
// 接這用2繼續跟7比,再跟1比,發現1較小,把1換到第一個位置。

1, 6, 3, 7, 2, 4, 5
// 接著用1繼續跟最後的4和5比,1仍然是最小,留在第一位。

用這樣的方式比較完一輪後,可以確定的是最小的牌會在第一個位置,那麼可以說第一個位置已經排序完成,不用再檢查或移動了。接著從第二個位置開始,進行跟剛剛一樣的比較,全部比完後,第二個位置也排好了,再從第三個位置開始...

1, 2, 6, 7, 3, 4, 5
// 第二輪比完後的狀態

1, 2, 3, 7, 6, 4, 5
// 第三輪比完後的狀態

像這樣比較下來,等於每一輪會排好一個數字,那麼比到最後一輪剩下一個數字時,就會完成排序。

這樣的演算法叫做選擇排序,它的步驟其實就是不斷地從未排序的元素中選出最小(或最大)的,排在排序好的數列末尾,直到所有數字都排序完成。

不過從剛剛的例子中大概也可以感覺得出來,這種直觀的演算法速度頗慢。可以把它想成當總共有n個元素,就得比較n輪,每一輪又得全部元素都檢查一遍,所以它的執行時間是O(n²)。[註1]

而且選擇排序還有一個缺點。因為一次只能檢查一個位置,所以任何數列都只能經過每一輪逐一比較,才能知道結果。也就是說,就算你給電腦一個有序陣列,選擇排序還是無法加快,無論如何得經過n²次操作,等於執行時間最糟是O(n²),最佳還是Ω(n²)。

以下是選擇排序的動畫,紅色是當前最小的元素,黃色是已經排序好的元素:

圖片來源:維基百科

同樣是排序,下一回我們會看到思考方式不太一樣的泡沫排序演算法。


  • [註1]嚴格來說,因為每一輪會排好一個數字,所以每一輪需要檢查的元素會減一,總共檢查的次數是n+(n-1)+(n-2)+...+1,這個總和是(n²+n)/2,執行時間仍是O(n²)。

上一篇
Day 05:到底有多壞?演算法的最壞情況執行時間
下一篇
Day 07:泡沫排序(bubble sort)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言