歡迎來到排序演算法的世界！
哈囉，未來的電腦科學家們！本章節要探討的是排序（Sorting）——電腦運算中最基本且最重要的概念之一。別擔心「演算法（Algorithm）」這個詞聽起來很複雜，它其實就只是一套清晰明確的指令步驟而已。
你會學到什麼？ 你將會學習電腦用來排列數據的三種經典方法，一步步理解它們的運作原理，並探討為什麼有些方法比其他方法更快。
為什麼這很重要？ 試想一下，如果你要在字典中查找一個詞，但裡面的詞是隨機排列的，或者你的手機通訊錄完全沒有依照字母順序排列，那會有多麻煩！排序讓搜尋變得快速且高效。當數據經過排序後，電腦幾乎可以瞬間找到所需的資訊。
I. 核心概念：什麼是排序演算法？
排序的目標
排序演算法是一種處理過程，它將輸入的項目列表重新排列，使它們呈現特定的順序（例如升序：1, 2, 3，或是降序：Z, Y, X）。
- 輸入 (Input)： 一組未排序的項目（例如：[5, 2, 8, 1]）。
- 過程 (Process)： 排序演算法運用比較與交換的規則。
- 輸出 (Output)： 已排序的列表（例如：[1, 2, 5, 8]）。
先修概念：交換 (Swapping)
我們接下來要介紹的所有排序法，都依賴於對項目進行交換。交換是指將列表中兩個元素的位置互換。
範例：如果列表 A[1] = 5 且 A[2] = 2，交換後，A[1] = 2 且 A[2] = 5。
II. 氣泡排序 (Bubble Sort) —— 最簡單的排序
氣泡排序通常是學生學習的第一種演算法，因為它最容易理解，儘管它在現實世界的高效能系統中很少被直接使用。
比喻：冒泡上升
想像你有一杯汽水，細小輕盈的氣泡會迅速上升到頂部。在氣泡排序中，最大（或最小）的元素會像氣泡一樣，經過多次遍歷後「浮」到它們正確的位置。
氣泡排序的運作方式（逐步教學）
氣泡排序會反覆遍歷列表，比較相鄰（彼此相鄰）的元素，如果順序錯誤就交換它們。
過程詳解：
- 從列表開頭開始。
- 比較第一個項目與第二個項目。
- 如果它們順序不對，就交換它們。
- 移動到下一對（第二個與第三個），比較，若有需要則交換。
- 持續這個過程直到到達列表末尾。這完成了一次遍歷 (Pass)。
- 經過第一次遍歷後，最大的項目絕對會到達列表末尾的正確位置。
- 重複整個過程（第二次遍歷、第三次遍歷等），但停止比較列表末尾已經排好序的元素。
- 當完成一次完整的遍歷且零次交換發生時，演算法結束。
快速複習：氣泡排序
核心動作： 比較並交換相鄰項目。
優點： 易於理解與編寫代碼。
缺點： 對於大型列表非常慢，因為它執行了大量的比較與交換。
III. 插入排序 (Insertion Sort) —— 玩紙牌排序
插入排序通常是人類在整理小量列表時會自然使用的方法，就像排列手中的紙牌一樣。
比喻：整理紙牌
當你拿起紙牌時，你會拿出一張新牌，並將它滑入你手中已排好序的牌組中的正確位置。
插入排序的運作方式（逐步教學）
插入排序將列表分為兩部分：已排序區（在左側）和未排序區（在右側）。
過程詳解：
- 首先將第一個元素視為已已排序區（因為只有一個項目的列表永遠是排好序的）。
- 從未排序區取下一個元素（即第二個項目），這是關鍵值 (Key)。
- 將關鍵值與已排序區中的項目進行反向比較。
- 如果關鍵值小於已排序區中的某個項目，將該較大的項目向右移一個位置。
- 持續移動項目直到找到關鍵值的正確位置，然後將其插入該處。
- 重複步驟 2-5，直到所有來自未排序區的項目都插入到已排序區為止。
別擔心，一開始覺得有點棘手是很正常的！核心概念就是：取一個項目，在已排序的群組中找到它的位置，然後把其他東西滑開來挪出空間。
你知道嗎？
如果一個列表已經幾乎排序完成，插入排序會極快，因為它只需要移動元素極短的距離。
快速複習：插入排序
核心動作： 取出一個項目，並將其插入已排序列表中的正確位置。
優點： 對於小型列表或近乎排序完成的列表非常高效。
缺點： 對於大型、完全未排序的列表來說速度較慢，因為移動元素需要耗費時間。
IV. 選擇排序 (Selection Sort) —— 減少交換次數的排序
選擇排序非常直接，並能保證每次遍歷都能將一個項目放置在正確位置。它的重點在於找出未排序部分中的極值（最小值或最大值）。
比喻：挑選最佳球員
想像你在組建球隊。在第一輪中，你查看*所有*可選的人（整個列表），並選出最優秀的一位（最小值）。你將這位球員放在第一個位置，然後忽略他，接著對剩餘的球員重複上述過程。
選擇排序的運作方式（逐步教學）
過程詳解：
- 從第一個位置（索引 0）開始。這裡是最小項目要放置的地方。
- 搜尋剩餘整個列表，找出絕對的最小值。
- 一旦找到最小值，就將它與目前起始位置（索引 0）的項目進行交換。
- 現在，索引 0 已經排好序並被鎖定。
- 移動到下一個起始位置（索引 1）。
- 搜尋剩餘的未排序部分（從索引 1 開始）找出新的最小值。
- 將此新的最小值與目前索引 1 的項目進行交換。
- 重複此選擇與交換的過程，直到整個列表排序完成。
避免常見錯誤：
選擇排序不會像氣泡排序那樣進行許多小額交換。它在每次遍歷只進行一次主要交換，確保每次搜尋完成後都有一個元素被放到了最終位置。
快速複習：選擇排序
核心動作： 從未排序列表中選擇最小值，並交換到正確位置。
優點： 需要的交換次數最少（總共 N-1 次交換，其中 N 為項目數）。如果數據交換非常耗時，這可以節省時間。
缺點： 它在每次遍歷時都必須檢查未排序列表中的*每一個元素*，這使得它在處理大型列表時效率不高。
V. 比較演算法效率
在電腦科學中，當我們比較演算法時，通常會看它們有多高效。效率主要透過它們運行的速度（時間複雜度 Time Complexity）以及它們佔用的記憶體空間（空間複雜度 Space Complexity）來衡量。對於 GCSE，我們主要專注於時間複雜度。
理解時間複雜度（簡單術語）
時間複雜度告訴我們，當輸入列表的大小 (N) 增加時，演算法的運行時間會如何增長。
\(N^2\) 時間（平方時間）的問題
氣泡排序、插入排序（在最差情況下）以及選擇排序通常被稱為 \(O(N^2)\) 演算法（讀作 "Order N Squared"）。
- 如果你有 10 個項目 (N=10)，演算法大約需要 10 x 10 = 100 個步驟。
- 如果你有 1,000 個項目 (N=1,000)，演算法大約需要 1,000 x 1,000 = 1,000,000 個步驟！
步驟數量的巨幅增加，使得這三種排序法在面對龐大的數據集時非常緩慢。
排序效能總結
| 演算法 | 過程 | 最佳情況（近乎排序） | 最差情況（反向順序） |
|---|---|---|---|
| 氣泡排序 | 相鄰比較與交換。 | 仍然慢（大量遍歷）。 | 非常慢（大量交換）。 |
| 插入排序 | 將項目插入已排序區。 | 極快（最小移動量）。 | 慢（需要最大移動量）。 |
| 選擇排序 | 找出最小值並在每次遍歷交換一次。 | 慢（總是檢查每個元素）。 | 慢（總是檢查每個元素）。 |
重點總結
對於小型列表，這三種排序法之間的差異可以忽略不計。但當處理數百萬筆記錄（例如社交媒體數據或全球金融交易）時，我們需要比這些依賴 \(N^2\) 比較的方法快得多的演算法！
VI. 快速複習檢查
為了在此課題中取得好成績，請確保你能使用一個小型列表（例如：[4, 1, 3, 2]）描述每一種排序的精確步驟。
記憶小技巧
- Bubble Sort（氣泡排序）：比較成對的兩邊 (Both sides)（相鄰）。
- Insertion Sort（插入排序）：每次將一個項目插入 (Inserts)到已排序區（就像紙牌一樣）。
- Selection Sort（選擇排序）：選擇 (Selects)最小值並將其交換到前端。
持續練習追蹤這些步驟，你很快就能精通這些演算法！祝你好運！