Sorting algorithms

歡迎來到排序的世界！

在本章中，我們將探討電腦如何將雜亂的數據整理成井然有序的列表。無論是按姓名排序通訊錄，還是按歌手排序音樂庫，排序算法（Sorting Algorithms）都是幕後的功臣。我們將專注於課程大綱要求的兩種特定方法：氣泡排序法（Bubble Sort）和合併排序法（Merge Sort）。別擔心這些術語聽起來很生硬——看完這些筆記後，你就能像專業人士一樣輕鬆處理它們了！

1. 氣泡排序法 (Bubble Sort)

氣泡排序法通常是學生學習的第一種排序算法。它非常易於理解，但正如你稍後會看到的，它並不是完成任務最高效的方法！

運作原理：類比說明

想像一排身高不同的學生，你想按從矮到高將他們排列。你從左邊開始，比較前兩名學生；如果左邊的學生比右邊的高，就讓他們交換位置。你對每一對學生重複這個動作，直到最高的學生像「氣泡」一樣浮動到隊伍的最末端。然後，你再從頭開始重複整個過程。

逐步邏輯

1. 從列表的開端開始。
2. 比較前兩個項目。
3. 如果第一個項目大於第二個，就交換它們。
4. 移動到下一對並重複此步驟，直到到達列表末端（這稱為一輪（Pass））。
5. 對整個列表重複上述過程，直到無需再進行任何交換為止。

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

標準的氣泡排序法可能非常慢。課程要求你掌握兩種使其更高效的方法：

• 縮小搜尋範圍：第一輪結束後，最大的項目必定已到達末端。第二輪後，最大的兩個項目都已到位。因此，每一輪過後，我們檢查的項目數量都可以減少一個。
• 使用「交換標記（Swapped flag）」：如果我們進行完整的一輪後沒有發生任何交換，這意味著列表已經排序完成！我們可以使用不定次數迭代（Indefinite iteration）（例如 While 迴圈）來提早結束算法。

應避免的常見錯誤

「差一錯誤（Off-by-One Error）」：編寫氣泡排序代碼時要記住，如果列表有 \(n\) 個項目，你只需要比較 \(n-1\) 對。如果你嘗試將最後一個項目與其「右邊」的某個東西進行比較，程式就會崩潰，因為右邊根本沒有項目！

快速回顧：氣泡排序法編寫簡單，但對於大量數據而言效率低下。它在處理「已接近排序」的列表時表現最好。

2. 合併排序法 (Merge Sort)

如果說氣泡排序法是一個緩慢的「冒泡」過程，那麼合併排序法則使用了一種更聰明的策略，稱為分治法（Divide and Conquer）。

運作原理：類比說明

想像你有一副凌亂的撲克牌。與其一次排序整副牌，不如將它分成兩半。接著再將這兩半繼續對半分，直到變成 52 張單獨的牌。由於單張牌本身就是「已排序」的，你就可以開始按正確順序將它們合併（Merging）回來。

兩個階段

1. 分割階段（Divide Phase）：將列表反覆對分，直到每個子列表只剩下一個項目為止。
2. 合併階段（Merge Phase）：將子列表重新合併。合併兩個列表時，電腦會比較兩者的第一個項目，並將較小的一個放入新的合併列表中。重複此步驟，直到最後剩下一份完全排序好的列表。

合併排序演示

假設我們有列表 [8, 3, 5, 1]：
• 分割： [8, 3] 和 [5, 1]
• 再次分割： [8], [3], [5], [1]
• 合併（第一輪）： [3, 8] 和 [1, 5]
• 合併（第二輪）： 比較 3 和 1（1 較小），然後比較 3 和 5（3 較小），然後比較 8 和 5（5 較小），最後剩下 8。結果為：[1, 3, 5, 8]。

重點提示：你不需要在 AS Level 考試中編寫合併排序的代碼，但你必須能夠透過圖表或追蹤表（Trace table）展示其分割和合併數據的過程。

3. 算法比較

在考試中，你可能會被問到為何選擇其中一種算法。以下是詳細分析：

時間效率

• 氣泡排序法：對於大型列表非常慢。其效能很大程度上取決於起始順序。如果列表已排序，優化後的氣泡排序速度非常快；但如果是反序，那簡直是一場災難！
• 合併排序法：對於大型列表快得多。它的效能非常穩定，無論列表是已排序還是完全隨機，所需的時間大約相同。

記憶體（空間）效率

• 氣泡排序法：對記憶體非常友好！它在「原地（In-place）」進行排序，意味著不需要建立數據的額外副本。
• 合併排序法：會佔用更多記憶體，因為它在「分割」階段必須建立許多小的子列表。

「你知道嗎？」

合併排序法由現代電腦架構之父之一約翰·馮·紐曼（John von Neumann）於 1945 年發明。至今，它仍然是專業軟體中最流行的排序方法之一！

4. 總結表

算法：氣泡排序法 (Bubble Sort)
適用場景：小型列表或已接近排序的數據。
主要優點：編寫簡單；記憶體佔用極少。
主要缺點：對於大型、未排序的數據集非常慢。

算法：合併排序法 (Merge Sort)
適用場景：對速度有要求的數據集。
主要優點：速度快且效能穩定。
主要缺點：需要更多記憶體來儲存子列表。

記憶法：S 規則

• Bubble（氣泡）很 Basic（基礎），但對於大數據來說很 Bad（糟糕）。
• Merge（合併）很 Modern（現代），而且速度 Much（快得多）。

成功的小秘訣：追蹤氣泡排序法時，請務必畫底線標示你當前正在比較的對象。追蹤合併排序法時，畫出分割與合併的「樹狀」結構——這能讓你更清楚地掌握數字的移動路徑，不容易出錯！