歡迎來到排序演算法的世界！

哈囉，未來的電腦科學家們！本章節要探討的是排序（Sorting）——電腦運算中最基本且最重要的概念之一。演算法（Algorithm）其實就只是一套用來解決問題的清晰、逐步的指令而已。

你會學到什麼？ 你將會學習課程大綱所要求的兩種核心排序演算法：氣泡排序（Bubble sort）與合併排序（Merge sort）。你將會一步步理解它們的運作原理，並比較它們各自的優點和缺點。

為什麼這很重要？ 試想一下，如果你要在字典中查找一個特定的詞，但裡面的詞是隨機排列的，或者要在手機通訊錄中搜尋一個完全沒有依照字母順序排列的聯絡人，那會有多麻煩！排序讓搜尋變得快速且高效。當數據經過排序後，電腦尋找資訊的速度會快得多。

I. 核心概念：什麼是排序演算法？

排序的目標

排序演算法是一種處理過程，它將輸入的項目列表重新排列，使它們呈現特定的順序（例如升序：1, 2, 3，或是降序：Z, Y, X）。

• 輸入 (Input)： 一組未排序的項目（例如：[5, 2, 8, 1]）。
• 過程 (Process)： 排序演算法運用比較、交換或分割／合併的規則。
• 輸出 (Output)： 已排序的集合（例如：[1, 2, 5, 8]）。

先修概念：交換 (Swapping)

像氣泡排序這樣的演算法，都依賴於對項目進行交換。交換是指將列表中兩個元素的位置互換。
範例：如果列表 List[A] = 5 且 List[B] = 2，交換後，List[A] = 2 且 List[B] = 5。

II. 氣泡排序 (Bubble Sort)

氣泡排序是其中一種最容易理解和實作的排序演算法。

比喻：冒泡上升

想像你有一杯汽水，氣泡會上升到表面。在氣泡排序中，最大的元素會像氣泡一樣，經過多次遍歷後逐漸「浮」到列表的末尾。

氣泡排序的運作方式（逐步教學）

氣泡排序會反覆遍歷列表，比較相鄰（彼此並排）的元素，如果順序錯誤就交換它們。

過程詳解：

1. 從列表開頭開始。
2. 比較第一個項目與第二個項目。
3. 如果它們順序不對，就交換它們。
4. 移動到下一對相鄰項目（第二個與第三個項目），進行比較，若有需要則交換。
5. 持續這個過程直到到達列表末尾。這完成了一次遍歷 (Pass)。
6. 經過第一次遍歷後，最大的項目絕對會到達列表末尾的正確最終位置。
7. 對後續的遍歷（第二次遍歷、第三次遍歷等）重複整個過程。
8. 當完成一次完整的遍歷且零次交換發生時，演算法結束，這表明列表已經完全排序好。

快速複習：氣泡排序

核心動作： 比較並交換相鄰項目。
優點： 易於理解，易於編寫代碼，且只需要極少額外的記憶體。
缺點： 對於大型列表非常低效且緩慢，因為它執行了大量的比較與交換（最差情況下的時間複雜度為 \( O(N^2) \)）。

III. 合併排序 (Merge Sort)

合併排序是一種基於分治法（Divide and Conquer）策略且高效得多的演算法。

比喻：分工合作

想像你有一大疊未整理的試卷。試圖一次過整理整疊試卷會讓人不知所措。相反，你將整疊試卷分成兩半，將每一半交給一名助手繼續拆分並排序，然後再整齊地將排好序的較小試卷堆合併在一起。

合併排序的運作方式（逐步教學）

合併排序分為兩個不同的階段運作：分割階段 (Divide Phase)（拆分列表）和合併階段 (Merge Phase)（依順序重新組合它們）。

1. 分割階段：

1. 取出未排序的列表，並將其分成相等（或近乎相等）的兩半。
2. 繼續反覆將每個子列表對半分割，直到每個子列表只包含一個單一元素。
3. 根據定義，只包含一個元素的列表本身就是已經排好序的。

2. 合併階段：

1. 取出相鄰的單一項目列表並成對進行合併，比較它們的元素，使新組合的列表處於已排序的狀態。
2. 對兩項目列表對、四項目列表對等重複此合併過程。
3. 繼續合併已排序的子列表，直到只剩下一個完全排好序的列表為止。

快速複習：合併排序

核心動作： 遞迴地將列表分割至單一項目，然後按排序好的順序將它們合併回來。
優點： 對於大型數據集，速度明顯更快且效能比氣泡排序更穩定。
缺點： 理解和實作起來較為複雜；在合併過程中需要額外的記憶體空間來存放分割後的子列表。

IV. 比較氣泡排序與合併排序

在電腦科學中，比較演算法能讓我們為特定問題選擇合適的工具。我們主要根據演算法在不同列表大小下的執行速度和效率來進行評估。

比較總結

特徵 / 氣泡排序 / 合併排序
• 方法： 氣泡排序採用反覆的相鄰比較與交換；合併排序採用分治法（分割與合併）。
• 速度／效率： 氣泡排序在大型列表上較慢，時間呈平方級增長（\( O(N^2) \)）；合併排序在大型列表上快速且高效。
• 記憶體使用量： 氣泡排序只需極少額外記憶體（就地排序）；合併排序需要額外記憶體來儲存子列表。
• 實作難度： 氣泡排序編寫簡單直接；合併排序演算法結構較複雜。

重點總結

對於極小的列表，氣泡排序很容易編寫且完全夠用。然而，對於海量數據，合併排序則優秀得多，因為隨著項目數量（\( N \)）的增加，它的運行時間增長速度要慢得多。

V. 快速學習複習

為了在此課題的考試題目中取得好成績，請確保你能使用一個小型列表（例如：[6, 3, 8, 2, 5]）逐步追蹤氣泡排序和合併排序的過程，並能清楚解釋各自的優點和缺點。

記憶小技巧

• 氣泡排序 (Bubble Sort)： 尋找相鄰對互換位置，直到出現一次 0 次交換的遍歷為止。
• 合併排序 (Merge Sort)： 尋找將列表分割至單一項目，接著成對合併為已排序順序的過程。

持續練習追蹤這些步驟，你將能滿懷信心地精通排序演算法！