第 3.4.2 章：排序演算法——化混亂為秩序

哈囉！歡迎來到排序演算法的世界。在這裡，我們將學習電腦如何將雜亂無章的數據整理成井然有序、方便使用的列表。試想一下，如果你要在一個完全沒有分類的圖書館裡找一本書，那簡直是天方夜譚！排序數據能讓搜尋（你在上一節剛學過！）等任務變得極其快速。

在本章中，我們將深入探討兩種主要的排序演算法：簡單但緩慢的氣泡排序法（Bubble Sort），以及強大且快速的合併排序法（Merge Sort）。你需要精確掌握它們的運作方式、如何按步驟追蹤（Trace）它們，以及它們在效率上的差異。讓我們開始吧！


1. 氣泡排序法 (Bubble Sort)

氣泡排序法大概是最容易理解的排序演算法，但它也是最沒效率的方法之一。它的運作方式是不斷遍歷列表，比較相鄰的元素，如果順序錯誤就交換它們。

1.1 氣泡排序法如何運作：類比法

想像你在水中有成串的氣泡，每個氣泡代表一個數字。較大的氣泡會升得更快。氣泡排序法的運作方式正是如此：在每一輪遍歷中，剩餘未排序的最大元素會像氣泡一樣「浮」到列表末端的正確位置上。

1.2 按步驟追蹤（基礎版）

氣泡排序法由多次對數據的遍歷（Pass）組成。在每一輪遍歷中，我們使用迴圈來迭代處理所有相鄰的配對。

讓我們來追蹤這個列表：[5, 1, 4, 2]

第一輪遍歷 (Pass 1)

  • 比較 5 和 1。(5 > 1)。交換。列表變為：[1, 5, 4, 2]

  • 比較 5 和 4。(5 > 4)。交換。列表變為：[1, 4, 5, 2]

  • 比較 5 和 2。(5 > 2)。交換。列表變為：[1, 4, 2, 5]

    最大的元素 (5) 現在已正確放置在列表末尾。

第二輪遍歷 (Pass 2)

  • 比較 1 和 4。(1 不大於 4)。不交換。列表：[1, 4, 2, 5]

  • 比較 4 和 2。(4 > 2)。交換。列表變為：[1, 2, 4, 5]

  • 比較 4 和 5。（我們只需要檢查到倒數第二個項目，因為最後一個項目 (5) 已經排序完成。但在基礎版本中，我們可能會照樣檢查。）

    第二大的元素 (4) 現在也已正確放置。

第三輪遍歷 (Pass 3)

  • 比較 1 和 2。不交換。列表：[1, 2, 4, 5]

  • 比較 2 和 4。不交換。列表：[1, 2, 4, 5]

由於在第三輪中沒有進行任何交換，說明列表已經完成排序，演算法可以停止（如果使用優化版本的話，請見下文）。

快速複習：氣泡排序法流程

氣泡排序法使用迭代（Iteration）（迴圈）重複比較相鄰元素，若順序錯誤則進行交換，直到整個列表排序完成。

1.3 提升氣泡排序法的效率（優化）

標準實作使用的是定數迭代（Definite Iteration）（固定次數的遍歷）。然而，我們可以透過兩個關鍵改進來提升效率：

  1. 減少檢查次數： 在每一輪完整的遍歷後，未排序項目中最大的那個一定會到達最終正確位置。因此，在下一輪遍歷中，我們能將檢查項目的數量減少一個。

  2. 提早結束（非定數迭代）： 如果完成了一整輪遍歷後，沒有發生任何交換，說明列表已經完全排序好了。我們可以使用布林旗標（Boolean flag，例如 swapped = False），並將整體迴圈從定數迭代改為非定數迭代（Indefinite Iteration）（例如使用 WHILE 迴圈，只要有發生交換就繼續）。這使得排序過程可以在沒有進行任何交換的那一輪遍歷後立即停止。

你知道嗎？ 氣泡排序法的時間效率很大程度上取決於列表開始時的排序程度。如果列表已經部分有序，優化版本（帶有提早結束功能）會非常快地完成！

氣泡排序法重點摘要： 它非常容易編寫（你可能會被要求寫出其程式碼！），但效率較低，特別是在列表很大且非常雜亂的時候。它的主要優勢在於，若數據已經排序好（使用優化後），它能迅速結束。


2. 合併排序法 (Merge Sort)

合併排序法比氣泡排序法更先進且速度快得多。它是分治法（Divide and Conquer）的一個經典範例。

2.1 合併排序法如何運作：分治法

合併排序法主要分為兩個階段：

  1. 分割（Divide）： 不斷將列表對半拆分，直到得到許多只包含一個元素的小列表。根據定義，只有一個元素的列表本身就是已排序的。

  2. 征服（Conquer / Merge）： 將這些小列表以排序的方式反覆合併，直到最終只剩下一個完整的已排序列表。

類比：想像要整理一大疊資料夾。與其比較相鄰的檔案，你將這疊資料夾分成兩小疊，分別交給兩個朋友，請他們各自負責整理好自己那一疊。當他們交回已排序好的小疊時，你只需要快速將這兩疊已排序的資料夾合併成一大疊即可。

2.2 按步驟示範（追蹤）

讓我們用列表：[8, 3, 1, 6, 9, 2] 來示範合併排序法的運作。

第一階段：分割 (The Divide)

我們遞迴地將列表對半拆分，直到只剩下單個元素。

  • 開始：[8, 3, 1, 6, 9, 2]

  • 第一次分割：[8, 3, 1] | [6, 9, 2]

  • 第二次分割：[8] | [3, 1] | [6] | [9, 2]

  • 第三次分割（到達基準情況）：[8] | [3] | [1] | [6] | [9] | [2]

第二階段：合併 (The Conquer)

我們合併相鄰的單元素列表，確保合併後的列表是有序的。

  • 第一次合併：[3, 8]（合併 [8] 與 [3]） | [1, 6]（合併 [1] 與 [6]） | [2, 9]（合併 [9] 與 [2]）

  • 第二次合併：[1, 3, 6, 8]（合併 [3, 8] 與 [1, 6]） | [2, 9]

  • 第三次合併（最終合併）：[1, 2, 3, 6, 8, 9]（合併 [1, 3, 6, 8] 與 [2, 9]）

注意：合併排序法的關鍵在於「合併」操作本身。你需要比較兩個已排序子列表的第一個元素，並重複選出較小的一個放入新的合併列表中。

合併排序法重點摘要： 合併排序法保證了快速的排序時間，因為它能有效地分割問題。你只需要能夠用一組數據解釋或示範其運作方式即可；考試中不會要求你編寫其程式碼。


3. 比較排序演算法的效率

當我們比較演算法時，我們會根據時間和記憶體使用量來評估它們的效率。

3.1 時間效率 (速度)

時間效率衡量的是執行時間隨輸入數據大小（通常記為 n）增加而成長的方式。我們使用 Big O 表示法（Big O notation） 來正式比較成長率（這是 A-Level 的要求）。

  • 氣泡排序法：

    • 最差情況時間複雜度： \(O(n^2)\)。這非常慢。如果你將列表大小 (n) 加倍，所需時間會增加四倍 (\(n^2\))。

    • 最佳情況時間複雜度： \(O(n)\)。如果列表已經排序（且我們使用了優化），它只需進行一次與 n 成正比的遍歷來檢查所有項目。

  • 合併排序法：

    • 最差情況時間複雜度： \(O(n \log n)\)。這非常快。對於大型數據集，它的擴展性比 \(O(n^2)\) 好得多。

    • 最佳情況時間複雜度： \(O(n \log n)\)。無論列表是否已排序，合併排序法通常都需要大約相同的時間。

時間效率總結： 對於大型、未排序的數據集，合併排序法通常比氣泡排序法快得多，因為 $O(n \log n)$ 的成長率優於 $O(n^2)$。

記憶小撇步：為什麼合併排序法更快？

氣泡排序法浪費時間重複比較已經檢查過的配對，特別是在元素需要移動到列表很遠的地方時。合併排序法避免了這一點，因為它只合併那些已知已經排序好的兩個列表。

3.2 空間效率 (記憶體使用量)

空間效率衡量的是一個演算法除了輸入列表本身之外，還需要多少額外的記憶體。

  • 氣泡排序法： 幾乎不需要額外的記憶體（只需幾個變數來記錄交換和指標）。它是原地（In-place）排序數據的。

  • 合併排序法： 需要與輸入列表大小成正比 (\(O(n)\)) 的額外記憶體，因為在合併過程中，它需要臨時儲存空間來存放子列表。

空間效率總結： 氣泡排序法在記憶體使用量（空間）方面比合併排序法更有效率，因為合併排序法在合併步驟中需要大量的臨時空間。


效率比較總結表

（比較氣泡排序法與合併排序法）

特性： 時間效率（最差情況）

氣泡排序法： $O(n^2)$（慢）

合併排序法： $O(n \log n)$（快）

特性： 對初始排序順序的依賴

氣泡排序法： 有。若已部分有序，會更快結束（最佳情況 $O(n)$）。

合併排序法： 沒有。無論如何皆為 $O(n \log n)$。

特性： 空間效率

氣泡排序法： 極佳（原地排序，記憶體使用量低）。

合併排序法： 較差（合併時需要 $O(n)$ 的額外記憶體）。

最終重點摘要： 如果你有龐大的數據集且速度至關重要，請使用合併排序法。如果你的記憶體空間極度受限，或者預期數據大部分已經排序好了，氣泡排序法（優化版）可能是一個較好的選擇。