歡迎來到排序演算法的世界！
在本章中，我們將學習電腦是如何將數據進行排序的。無論是遊戲中的高分列表、手機裡的通訊錄，還是購物網站上的商品，電腦都是透過排序演算法來整理資訊的。如果起初覺得這聽起來很「數學」，別擔心——它其實就像整理一副凌亂的紙牌一樣簡單！
我們將重點探討 AQA GCSE 考試中最重要的兩種演算法：冒泡排序法 (Bubble Sort) 和 合併排序法 (Merge Sort)。
1. 冒泡排序法 (Bubble Sort)
冒泡排序法通常是學生學習的第一個演算法，因為它非常直觀。它的運作原理是將列表中的最大值像氣泡一樣，一個接一個地「浮」到列表的末端。
運作流程：逐步解析
假設我們有一個數字列表：[5, 2, 4, 1]
步驟 1：比較前兩個數字（5 和 2）。因為 5 大於 2，所以我們將它們交換 (swap)。
列表現在變為：[2, 5, 4, 1]
步驟 2：比較下一組（5 和 4）。因為 5 大於 4，所以我們將它們交換。
列表現在變為：[2, 4, 5, 1]
步驟 3：比較最後一組（5 和 1）。因為 5 大於 1，所以我們將它們交換。
列表現在變為：[2, 4, 1, 5]
你有發現嗎？數字 5 已經像氣泡一樣「浮」到了列表末端的正確位置！這就是第一輪遍歷 (pass) 的結束。現在，演算法會從頭開始重複這個過程，直到不再需要任何交換為止。
記憶小撇步：碳酸飲料
想像一下氣泡飲料。最大的「氣泡」（最大的數字）會最先浮到頂部（列表的末端）！
快速回顧：冒泡排序法的機制
• 它會比較相鄰 (adjacent) 的項目（彼此相鄰的項目）。
• 如果它們順序錯誤，就進行交換。
• 它需要對列表進行多次遍歷。
• 當某一次遍歷過程中完全沒有進行任何交換時，排序即告完成。
重點總結：冒泡排序法容易理解且幾乎不需要額外的記憶體空間，但在處理長列表時速度會非常慢。
2. 合併排序法 (Merge Sort)
合併排序法就聰明多了。它被稱為分治法 (Divide and Conquer) 演算法。它不是一個一個地交換項目，而是先將列表拆分成極小的片段，然後再按正確順序將它們組裝回來。
運作流程：兩個主要階段
階段 1：分割 (Divide)
演算法會不斷將列表對半分，直到每個項目都變成獨立的微小列表。例如，[5, 2, 4, 1] 會變成 [5]、[2]、[4] 和 [1]。
階段 2：征服與合併 (Conquer/Merge)
現在，它開始將這些微小列表重新合併。每次合併兩個列表時，它都會將數字按正確順序排列：
1. [5] 和 [2] 合併變成 [2, 5]
2. [4] 和 [1] 合併變成 [1, 4]
3. 最後，將 [2, 5] 和 [1, 4] 合併成 [1, 2, 4, 5]
現實生活的類比：整理衣物
想像你有成堆的襪子。如果你試圖一次過整理整堆襪子，會很混亂。但如果你將大堆襪子分成小堆，先整理好小堆，最後再將它們拼在一起，速度就會快得多！
你知道嗎？
合併排序法是遞迴 (recursive) 的。這意味著演算法會呼叫自身的版本，來處理在「分割」階段產生的較小次列表！
重點總結：對於大量數據，合併排序法比冒泡排序法快得多；但它比較複雜，且因為需要建立新的次列表，會佔用較多的記憶體。
3. 比較：冒泡排序法 vs. 合併排序法
在考試中，你可能會被要求比較這兩種方法。以下是它們優缺點的簡單分析。
冒泡排序法
優點：
1. 編寫和理解起來非常簡單。
2. 幾乎不需要額外記憶體（它是「原地」排序）。
缺點：
1. 對於長列表非常缺乏效率且緩慢。
2. 因為必須多次重複掃描同一列表，所以耗時較長。
合併排序法
優點：
1. 對於大型列表，速度快且效率更高。
2. 運行時間穩定（無論初始列表有多混亂，表現都很一致）。
缺點：
1. 程式編寫較為複雜。
2. 使用更多記憶體，因為需要儲存所有較小的次列表。
常見錯誤陷阱
學生常認為冒泡排序法比較好，因為它比較簡單。千萬別掉入這個陷阱！在計算機科學中，「更好」通常代表「處理大數據的速度更快」。而在這場競賽中，合併排序法每次都勝出。
重點總結：在列表非常小或記憶體極度受限的情況下，請使用冒泡排序法。除此之外，特別是在處理大型資料庫時，請使用合併排序法！
快速檢查：哪個是哪個？
如果在考題中看到這些關鍵字，你就知道它們在談論哪個演算法了：
• 「相鄰項目」(Adjacent items) 或 「交換」(Swapping) → 冒泡排序法
• 「分治法」(Divide and Conquer) 或 「分割與合併」(Splitting and Merging) → 合併排序法
你一定做得到的！排序只不過是電腦為了釐清混亂所遵循的一套規則。繼續練習這些逐步的交換與分割，你很快就會成為排序專家！