Sorting algorithms

排序演算法簡介

歡迎！在本章中，我們將探討計算機科學中最基礎的任務之一：排序 (Sorting)。無論你是要在 Amazon 上篩選最便宜的商品，還是瀏覽社交媒體上朋友的最新貼文，幕後都有排序演算法在處理這些數據，確保它們以正確的順序呈現。

對於 AQA A Level 課程，你需要掌握兩種特定的演算法：氣泡排序 (Bubble Sort) 和 合併排序 (Merge Sort)。我們將研究它們的運作方式、如何一步步進行演算，以及它們的效率如何。如果起初覺得有些抽象也不用擔心，我們會使用大量的現實生活比喻，讓你輕鬆掌握！

預備概念：請記住，陣列 (Array) 其實就是一個項目的列表。排序的過程就是將這些項目（通常是數字）重新排列為升序（從小到大）。

1. 氣泡排序 (Bubble Sort)

氣泡排序通常是學生學習的第一種排序演算法。它以簡單易懂著稱，但正如你之後會看到的，對於大量數據來說，它的速度並不快！

運作方式：「上升氣泡」比喻

想像汽水裡的一串氣泡。更大、更「重」的氣泡會浮到上面。在氣泡排序中，演算法會遍歷列表，比較相鄰的項目，如果順序錯誤就將它們交換 (Swap)。這個過程會不斷重複，直到最大的數字像「氣泡」一樣浮到列表的最末端。

步驟拆解

1. 從列表的最開頭開始。
2. 比較前兩個項目。
3. 如果第一個項目大於第二個，就進行交換。
4. 移動到下一對項目並重複此步驟，直到列表結束（這稱為一輪掃描/Pass）。
5. 對整個列表重複上述過程，直到某次掃描過程中完全沒有發生任何交換為止。

讓我們試著演練一次！

假設我們有這個列表：[5, 1, 4]

第一輪掃描 (Pass 1)：
• 比較 5 和 1。5 比 1 大，進行交換。列表變為：[1, 5, 4]
• 比較 5 和 4。5 比 4 大，進行交換。列表變為：[1, 4, 5]
數字 5 現在已經「浮」到了最後面！

第二輪掃描 (Pass 2)：
• 比較 1 和 4。1 較小，不交換。
• 比較 4 和 5。4 較小，不交換。
這一輪沒有進行任何交換，所以列表已經排序完成！

效率與複雜度

氣泡排序被認為是一種效率極低的演算法。如果你有一個包含 \(n\) 個項目的列表，你可能需要將每個項目與其他所有項目進行比較。

• 時間複雜度： \(O(n^2)\)（多項式時間）。
• 為什麼？ 因為它使用了巢狀迴圈 (Nested loops)——一個迴圈用來遍歷列表，另一個迴圈則持續重複進行掃描。

快速複習：
• 最適用於：非常小的列表，或是已經幾乎排好序的列表。
• 常見錯誤：以為掃描一次列表就排序完成了。你必須持續進行掃描，直到完全沒有發生交換為止！

關鍵要點：氣泡排序簡單但速度慢。其時間複雜度為 \(O(n^2)\)。

2. 合併排序 (Merge Sort)

對於大型列表，合併排序比氣泡排序快得多。它使用了一種聰明的策略，稱為分治法 (Divide and Conquer)。

運作方式：「撲克牌」比喻

想像你有一堆雜亂的 100 張撲克牌。要一次把它們全排好很難。但如果你把它們分成兩堆各 50 張，再分成四堆各 25 張，一直分下去直到剩下 100 堆各只有 1 張牌……嗯，只有 1 張牌的那一堆已經算「排好序」了！然後，你只需要小心地將這些堆按正確順序合併 (Merge) 回來即可。

分治階段

階段 1：拆分 (Divide)

演算法不斷將列表一分為二，直到每個子列表只剩下一個元素。根據定義，只有一個元素的列表本身就是排好序的。

階段 2：合併 (Conquer/Merge)

隨後，演算法將這些子列表合併回來。在合併過程中，它會比較每個子列表前端的項目，並將較小的一個先放入新的組合列表中。

演練合併排序

列表：[8, 3, 5, 1]

步驟 1 (拆分)： 分成 [8, 3] 和 [5, 1]。
步驟 2 (拆分)： 分成 [8], [3], [5], [1]。
步驟 3 (合併)： 將 [8] 和 [3] 合併為 [3, 8]。將 [5] 和 [1] 合併為 [1, 5]。
步驟 4 (合併)： 合併 [3, 8] 和 [1, 5]。比較 3 和 1（1 較小），然後比較 3 和 5（3 較小），接著比較 8 和 5（5 較小），最後剩下 8。結果：[1, 3, 5, 8]。

效率與複雜度

由於合併排序每次都會將列表對半分割，它的效率遠高於氣泡排序。

• 時間複雜度： \(O(n \log n)\)。
• 為什麼？ 「\(\log n\)」來自於我們能將列表對半分割的次數，而「\(n\)」則來自於將項目合併回來所需的處理工作。

你知道嗎？ 合併排序比氣泡排序需要更多的記憶體（空間複雜度），因為在過程中必須建立新的子列表！

關鍵要點：合併排序是一種「分治」演算法，時間複雜度為 \(O(n \log n)\)。

總結比較表

氣泡排序
• 方法：交換相鄰項目。
• 複雜度： \(O(n^2)\)。
• 效能：慢，處理大量數據時效率低下。

合併排序
• 方法：分治法 (Divide and Conquer)。
• 複雜度： \(O(n \log n)\)。
• 效能：快，處理大量數據時效率高。

快速複習：檢查你的理解

• 哪一種演算法是「分治法」的例子？（答案：合併排序）
• 氣泡排序的時間複雜度是多少？（答案： \(O(n^2)\)）
• 為什麼氣泡排序被認為效率低下？（答案：它需要多次掃描和比較，特別是當列表變大時。）
• 如果你有一個包含 100 萬用戶的龐大資料庫，你應該使用哪種排序？（答案：合併排序，因為對於較大的 \(n\) 值， \(O(n \log n)\) 比 \(O(n^2)\) 快得多。）

如果覺得演練合併排序的過程有點「遞迴」或繞口也不用擔心！只要記住核心概念：拆分到只剩單個，然後依序縫合起來。