Sorting algorithms

排序演算法簡介

歡迎！在本章中，我們將一起探討排序演算法 (Sorting Algorithms)。簡單來說，排序就是將項目按特定順序排列的過程，例如字母順序 (A-Z) 或數字順序 (1-10)。

為什麼這很重要呢？試想一下，如果電話簿裡的姓名不是按字母順序排列，要找一個人會有多困難！電腦需要對數據進行排序，以便之後能更快速地搜尋。我們將專注於 AQA 考試中最重要的兩種方法：氣泡排序法 (Bubble Sort) 和 合併排序法 (Merge Sort)。

1. 氣泡排序法 (Bubble Sort)

氣泡排序法是最容易理解的排序演算法之一。它的名稱由來是因為較大的數值會像汽水中的氣泡一樣，逐步「浮」到列表的末端！

運作原理（機制）

該演算法透過不斷地掃描列表來運作。以下是詳細步驟：

1. 檢查列表中的前兩個項目。
2. 如果順序錯誤，就將它們互換 (Swap)；如果順序正確，則保持不動。
3. 移動到下一對項目（第 2 和第 3 個項目），並重複比較。
4. 持續進行直到抵達列表末端。這個過程稱為一輪 (Pass)。
5. 演算法會重複進行這些輪次，直到某次完整的輪次中完全沒有進行任何互換。這就是它判斷列表已排序完成的方法！

現實生活中的例子

想像有四名學生排成一列，你想根據身高（由矮到高）對他們進行排序：[Dave (180cm), Alice (155cm), Chris (170cm), Bob (160cm)]。

第一輪：
- 比較 Dave 和 Alice。Dave 較高，所以互換。[Alice, Dave, Chris, Bob]
- 比較 Dave 和 Chris。Dave 較高，所以互換。[Alice, Chris, Dave, Bob]
- 比較 Dave 和 Bob。Dave 較高，所以互換。[Alice, Chris, Bob, Dave]
Dave 已經「冒泡」到最後了！

第二輪：
- 比較 Alice 和 Chris。順序正確，無需互換。
- 比較 Chris 和 Bob。Chris 較高，所以互換。[Alice, Bob, Chris, Dave]
- 比較 Chris 和 Dave。順序正確，無需互換。

第三輪：
- 比較 Alice 和 Bob。順序正確，無需互換。
- 比較 Bob 和 Chris。順序正確，無需互換。
- 比較 Chris 和 Dave。順序正確，無需互換。
第三輪沒有進行任何互換，列表排序完成！

快速複習：氣泡排序法

- 動作： 比較相鄰的項目並進行互換。
- 停止條件： 當完整的一輪中沒有任何互換時。
- 最適用於： 非常小的列表，或是幾乎已經排好序的列表。

常見錯誤： 學生常以為演算法在跑完一輪後就會停止。記住，通常需要多輪 (Multiple passes) 才能將每個項目放到正確的位置！

關鍵點： 氣泡排序法易於理解和編寫，但對於大量數據來說，速度通常很慢。

2. 合併排序法 (Merge Sort)

合併排序法對於大型列表來說，是一種快得多的演算法。它使用了一種稱為分治法 (Divide and Conquer) 的技術。它不是逐個互換項目，而是將列表拆分成微小的碎片，然後再按正確順序重新組裝。

運作原理（機制）

如果起初覺得有點複雜，別擔心！它主要分為兩個階段：

第一階段：分割 (Divide)
演算法會不斷將列表對半分，直到每個項目都成為獨立的微小列表（只有一個項目的列表，技術上來說已經是排序好的了！）。

第二階段：征服/合併 (Conquer/Merge)
演算法開始將這些微小的列表重新合併。每次合併兩個列表時，它都會將項目按正確順序排列。它會持續進行此過程，直到只剩一個完整且已排序的列表為止。

視覺類比

想像一副亂掉的紙牌。你把牌堆分成兩份，然後是四份、八份，直到你手上拿著單張牌為止。然後，你取出兩張牌並排好順序，接著將這兩對合併成一個已排序的四張牌組，依此類推。

你知道嗎？ 對於像社交媒體網站上所有用戶列表這樣龐大的數據集，合併排序法比氣泡排序法有效率得多。

快速複習：合併排序法

- 動作： 重複將列表對半分，然後按順序合併回來。
- 技術： 分治法 (Divide and Conquer)。
- 最適用於： 大型數據列表。

關鍵點： 合併排序法在大型列表中比氣泡排序法更快，但編程較困難，且因為必須建立許多子列表，會消耗更多電腦記憶體。

3. 比較這兩種演算法

在考試中，你可能會被問到為何選擇某種演算法而非另一種。以下是一個簡單的對比，幫助你做決定。

氣泡排序法

優點：
- 寫法和理解起來非常簡單。
- 不需要額外太多記憶體（它在「原地/In place」進行排序）。

缺點：
- 對於大型列表來說效率低（速度慢）。

合併排序法

優點：
- 即使處理海量列表也非常有效率（速度快）。
- 無論原始列表有多亂，其運行時間都相當穩定。

缺點：
- 編程較為複雜。
- 使用更多記憶體，因為過程中需要建立許多子列表。

記憶小撇步： 把 Bubble 看作 "Basic"（基本，簡單但慢），把 Merge 看作 "Modern"（現代，複雜但快）。

快速複習：效率

當我們談論這些演算法的「效率」時，通常是指時間效率 (Time Efficiency)，即電腦完成任務所需的時間。隨著列表長度增加，氣泡排序法完成任務所需的時間增加速度，遠比合併排序法快得多。

關鍵點： 對於只有 5 個項目的短列表，氣泡排序法完全沒問題。但對於 500 萬個項目的列表，你必須使用合併排序法！

總結檢查清單

你能夠做到以下幾點嗎？

- [ ] 解釋氣泡排序法如何利用輪次 (passes) 和互換 (swaps)？
- [ ] 描述合併排序法中使用的「分治法」？
- [ ] 說出氣泡排序法的一個優點？（易於編寫/佔用記憶體較少）
- [ ] 說出合併排序法的一個優點？（大型列表處理速度較快）