演算法 | 選擇排序 | 氣泡排序 | 合併排序 | 遞迴

上回提到，演算法是一種解決問題的方法。光是簡單的將數字有小排到大就有很多種不同的排序演算法可以選擇。這次，我們來介紹幾個常見的排序演算法，看看它們是怎麼運作的。

選擇排序（Selection Sort）：

我們先來看一個問題：如何把 [3, 1, 4, 2] 這組數字從小排到大？

選擇排序的邏輯很簡單：程式會先從頭到尾「掃描」一遍所有數字，找到當前範圍內最小的數字，然後把它和最左邊的數字交換 （swap）。接著，再從剩下的數字中找出最小值，重複這個過程，直到整個數列都排好為止。

示範程式

具體步驟：

1. 一開始，程式會檢查整個數列 [3, 1, 4, 2]，發現最小的數字是 1，然後把它和最左邊的 3 交換。交換後的結果是 [1, 3, 4, 2]。（補充：每次掃描到最小值，會先暫存在記憶體，例如一開始掃到 3 先存，但掃到 1 又替換成最小值是 1。
2. 接著，程式會只看剩下的部分 [3, 4, 2]，發現最小的數字是 2，再把它和當前最左邊的 3 交換。這次交換後，數列變成 [1, 2, 4, 3]。
3. 然後，再看剩下的 [4, 3]，最小值是 3，把它和 4 交換，最後得到排序完成的數列 [1, 2, 3, 4]。

小結：

選擇排序的運作方式其實很直觀，簡單來說就是不斷找最小值，再用交換的方式換到正確的位置。即使中間有數字已經是正確的順序，演算法還是會繼續完整地掃描整個數列，直到所有數字都排好。

計算選擇排序的步驟：

假設長度為 n 的數列，選擇排序的步驟如下：

• 第一次掃描：需要掃描所有 n−1 個數字，找到最小值。
• 第二次掃描：需要掃描剩下的 n−2 個數字，找到最小值。
• 第三次掃描：掃描剩下的 n−3 個數字，依此類推……

所以，總共的比較次數可以表示為：

(n−1)+(n−2)+(n−3)+⋯+1

這其實是一個等差數列的總和，數學上的表示為：

選擇排序的 Big O 為 O(n²)，其實不是效率很高的演算法。忘記 Big O 是什麼的朋友，請看上一篇解說。

演算法 | Big O 複雜度| Pseudocode 偽代碼

選擇排序偽代碼：

for i from 0 to n-1:
       find smallet number between numbers[i] and numbers[n-1] // 從第0項到最後一項
       swap smallet number with numbers[i] // 找到最小，就跟當前的最左邊交換

氣泡排序（Bubble Sort）：

氣泡排序是比較相鄰的兩個數字。如果前一個比後一個大，就交換位置。我猜應該是感覺就像氣泡啵啵啵，故命名為氣泡排序：

氣泡排序的特點：

氣泡排序每次都會讓最大的數到正確的位置，如果沒有任何交換的過程，就可以提前結束程式。例如 [1, 2, 3, 4] 就不用一直比。

我們還是用之前的例子 [3, 1, 4, 2]，來看氣泡排序的具體過程。

具體步驟：

1. 第一輪：程式會從數列的第一個數字開始，依次比較相鄰的兩個數字。如果前一個比後一個大，就交換位置：
2. • 3 和 1 比較，因為 3 > 1，所以交換，結果變成 [1, 3, 4, 2]。
   • 接著比較 3 和 4，因為 3 < 4，所以不交換。
   • 最後比較 4 和 2，因為 4 > 2，交換，結果變成 [1, 3, 2, 4]。
2. 第二輪：我們重複這個步驟，但這次可以忽略最後一個數字（4），因為它已經是最大的數了：
3. • 1 和 3 比較，因為 1 < 3，不交換。
   • 然後比較 3 和 2，因為 3 > 2，所以交換，結果變成 [1, 2, 3, 4]。
3. 第三輪：這時候，只剩下前兩個數字需要比較：
4. • 1 和 2 比較，因為 1 < 2，不需要交換。

這樣，數列就已經完全排序好了，最終結果是 [1, 2, 3, 4]。

挑戰題：寫出偽代碼

ｉ from n-1 to 1:  
     j from 0 to i-1:
if j > j+1:
     swap j and j+1

在氣泡排序中，會用到 i 跟 j 的迴圈。本題的目標是將 [5, 4, 6, 0, 1] 這個數列由小排到大。第一次我們先將 i 定在最右邊，而 j 從第一個元素開始比較。

第一輪比較 ( i=n-1 )：

• 起始點在數字 5，現在比較 5 和它旁邊的 4。
• 因為 4 比較小，所以交換兩個數字。
• 數列變為：[4, 5, 6, 0, 1]

接下來，我們繼續使用 j 比較相鄰的元素。

• 比較 5 和 6，5 比 6 小，所以不交換，數列保持不變：[4, 5, 6, 0, 1]
• 再比較 6 和 0，0 比 6 小，所以交換。
• 數列變為：[4, 5, 0, 6, 1]
• 最後比較 6 和 1，1 比 6 小，再次交換。
• 數列變為：[4, 5, 0, 1, 6]

第一輪結果：

到此為止，最大的數字 6 已經「冒泡」到了最後一位（最右邊）。下一輪就不用再比到6。

第二輪比較：

• i 移到倒數第二位，j 繼續從頭開始比較。
• 比較 4 和 5，因為 4 比 5 小，不交換。
• 接著比較 5 和 0，因為 0 比 5 小，所以交換。
• 數列變為：[4, 0, 5, 1, 6]
• 再比較 5 和 1，因為 1 比 5 小，再次交換。
• 數列變為：[4, 0, 1, 5, 6]

現在，第二大的數字 5 也移到了它的正確位置。

第三輪比較：

• i 再移到倒數第三位，繼續從頭比較。
• 比較 4 和 0，因為 0 比 4 小，交換。
• 數列變為：[0, 4, 1, 5, 6]
• 接著比較 4 和 1，因為 1 比 4 小，再次交換。
• 數列變為：[0, 1, 4, 5, 6]

到此為止，第三大的數字 4 也移到了正確的位置。

第四輪比較：

• 現在只剩下最後兩個數字需要比較。
• 比較 0 和 1，因為 0 比 1 小，不需要交換。

合併排序（Merge sort ) 與遞迴（Recursion）

把一個大問題分成很多小問題來解決，最後再把小問題的結果組合起來，解決原來的大問題。

• 把數列切對半：不斷地將數列分成兩半，直到每一部分只剩下一個元素。
• 排序並合併：當每一部分都分開成單個元素後，開始逐步將它們合併，並在合併的過程中把數字排好。

這裡的概念可以參考 CS50 的影片，會更清楚地理解。

也可以用這個網站玩玩看。

以下是圖示：

步驟 1: 分割數列

合併排序首先會將數列不斷地對半分割，直到每個部分只剩一個元素。因為圖示清楚，這部分我就不多論述。

步驟 2: 開始合併並排序

接下來，我們開始進行合併，並在合併過程中對數字進行排序。

第一次合併：

• 合併 [53] 和 [13]，因為 13 < 53，結果是 [13, 53]
• 合併 [43] 和 [10]，因為 10 < 43，結果是 [10, 43]

第二次合併：（注意這部分的合併）

• 最後將兩個已排序的部分 [13, 53] 和 [10, 43] 進行合併：
• • 比較 13 和 10，因為 10 < 13，所以結果先放 10。
  • 再比較 13 和 43，因為 13 < 43，所以結果放 13。
  • 然後比較 53 和 43，因為 43 < 53，結果放 43。
  • 最後只剩下 53，直接放進結果。
  • 合併結果是 [10, 13, 43, 53]

最終結果：

排序完成的數列是：[10, 13, 43, 53]

在合併排序的過程中，可能會使用到遞迴的概念，以下介紹遞迴的概念。

遞迴（Recursion）

遞迴就是一種程式自己呼叫自己的方法。在遞迴中，一個函式（或方法）會不斷地呼叫自己，直到滿足一個特定的「中止條件」，如果沒有中止條件會使程式當掉。

遞迴是一個效能不好的方式，所以在合併排序中通常也會使用迴圈（loop）的方式來取代遞迴，這種方式不需要不斷呼叫自己，而是通過反覆執行來完成任務。

以下示範用遞迴「持續往左切一半，直到只剩下一個數字」。

• 參考資料：演算法學習筆記：合併排序（Merge Sort）

那什麼時候停止呢？就是當切到只剩一個就會回傳該數字。

動態規劃、貪婪演算法觀念

除了以上的排序，還有其他的演算法。我來簡單介紹這兩個演算法的重點，若要再更細節可以再搜尋其他大神的文章。

1. 動態規劃 (Dynamic Programming)

動態規劃的重點在於 記住已經計算過的結果，先存在暫時的地方。這樣在未來如果再遇到相同的問題，就不用重新計算，節省時間。這個過程叫做 記憶化 (Memoization)。

舉例：找最短路徑

假設你在迷宮裡，要從起點走到終點。我們需要找到一條最短的路，避開障礙物並選擇最快的路徑。

• 當走到另一個分岔點時，如果需要知道從之前走過的位置到終點的距離，就可以直接使用之前記住的結果，不用重算。
• 當走到每個新位置時，可以根據已經計算好的結果來做出最好的選擇，節省時間。
• 以下圖來說，電腦會先記憶 A 到 B 的距離、A 到 C 的距離，如果詢問 A 到 D 的最短路徑，它就會根據加總的距離最小，給出答案為 A-C-D。

2. 貪婪演算法 (Greedy Algorithm)

貪婪演算法的特點是 每次只考慮當下的最好選擇，但它不會去想將來的情況。因此，貪婪演算法可以眼下最近的例子，但是以全局來說，可能不是最佳解。

舉例：找最短路徑

再來看看你在迷宮裡找最短路徑的例子。

• 如果你用貪婪演算法，當你站在一個分岔路口時，你只會選擇看起來最短的路，而不會考慮其他可能會更好但看起來比較遠的路。
• 以下圖來看，A 要到 D ，邏輯是向右選擇途徑。出發先看到最短距離是 C （1），走到 C 後最短距離是到 B （3），再向右 7 格到 D。但實際上最短的距離應該是 A C D 才對。

如果你對這些演算法有興趣，或者有什麼問題，歡迎在下方留言！讓我們一起學習、討論～ 👩‍💻👨‍💻