排序演算法簡介
歡迎閱讀這份關於排序演算法（Sorting Algorithms）的學習筆記！你有沒有試過在電子遊戲中搜尋最高得分、在手機中翻找通訊錄，或者把手中的撲克牌由小至大整理好？這一切其實都依賴「排序」。
在電腦科學中，電腦需要處理海量的數據。為了讓這些數據更容易被搜尋、閱讀和管理，我們會運用按部就班的程序——即演算法（Algorithms），把項目排列成特定的次序（例如由小至大的數值升序，或是由 A 至 Z 的字母順序）。
起初接觸時覺得有點複雜也不用擔心！我們會透過清晰的例子和生活化的比喻，一步步拆解每種演算法的運作原理。
重點摘要：排序演算法是一套循序漸進的指令，能將未經排序的項目清單重新排列成特定次序（例如數值升序或字母順序）。
計算思維與排序
排序演算法是實踐計算思維（Computational Thinking）的絕佳例子：
• 抽象化（Abstraction）：專注於關鍵細節（比較兩個數字並進行交換），同時忽略無關的資訊（例如數字是用甚麼顏色顯示）。
• 問題分解（Decomposition）：把「排序整份清單」這個大難題，拆解成較小且更易處理的步驟——例如每次只比較一對項目，或是將清單一分為二。
• 演算法思維與邏輯推理（Algorithmic Thinking & Logical Reasoning）：按部就班建立並遵循清晰的規則，並比較不同的演算法，找出最適合特定工作的一種。
理解「數值交換（Swap）」的邏輯
許多排序演算法都是透過在清單中「交換」兩個數值來運作。不過，電腦如何在不遺失數據的情況下交換兩個數值呢？
想像一下你有一杯橙汁（杯 \(A\)）和一杯蘋果汁（杯 \(B\)）。如果你直接把杯 \(B\) 倒進杯 \(A\)，兩種果汁就會混在一起，你亦會失去原本的橙汁！要安全地交換它們，你需要第三個空杯作為臨時容器（杯 \(temp\)）：
1. 把杯 \(A\) 的橙汁倒進杯 \(temp\)（\(temp = A\)）
2. 把杯 \(B\) 的蘋果汁倒進杯 \(A\)（\(A = B\)）
3. 把杯 \(temp\) 的橙汁倒進杯 \(B\)（\(B = temp\)）
在電腦編程中，這個臨時變數（temporary variable）能確保在交換過程中，不會有任何數據被覆蓋或遺失。
演算法 1：冒泡排序法（Bubble Sort）
冒泡排序法是最簡單的排序演算法之一。它的運作原理是重複走訪清單，每次比較相鄰（並排）的兩個項目，如果它們的次序錯誤就把它們交換。
冒泡排序法的運作步驟：
1. 從清單的最開頭開始。
2. 比較首兩個相鄰的項目（項目 \(1\) 和項目 \(2\)）。
3. 如果它們的次序不正確（例如在升序排列中，第一個項目大於第二個），就將它們交換（Swap）。如果次序本來就正確，則保持不變。
4. 移至下一對相鄰項目（項目 \(2\) 和項目 \(3\)），重複進行比較與交換。
5. 繼續沿著清單逐步進行，直至到達清單末尾。這代表完成了一輪走訪（Pass）。在第 1 輪走訪結束時，最大的數字就像氣泡一樣「浮」到了清單末端的正確位置。
6. 重複進行各輪走訪，直到在某一輪完整走訪中出現零次交換（0 swaps）為止。零次交換代表整份清單已經完全排序好！
逐步追蹤範例（Tracing Bubble Sort）：
讓我們以升序排列這份清單：[5, 1, 4, 2]。
第 1 輪走訪（Pass 1）：
• 比較 5 和 1：\(5 > 1\)，進行交換 \(\implies\) [1, 5, 4, 2]
• 比較 5 和 4：\(5 > 4\)，進行交換 \(\implies\) [1, 4, 5, 2]
• 比較 5 和 2：\(5 > 2\)，進行交換 \(\implies\) [1, 4, 2, 5]
第 1 輪結束狀態：[1, 4, 2, 5]（最大的數字 5 已經到達最終位置。因為期間進行過交換，所以我們必須進行下一輪走訪！）
第 2 輪走訪（Pass 2）：
• 比較 1 和 4：次序正確，無須交換 \(\implies\) [1, 4, 2, 5]
• 比較 4 和 2：\(4 > 2\)，進行交換 \(\implies\) [1, 2, 4, 5]
• 比較 4 和 5：次序正確，無須交換 \(\implies\) [1, 2, 4, 5]
第 2 輪結束狀態：[1, 2, 4, 5]（期間進行過交換，因此我們必須再次檢查！）
第 3 輪走訪（Pass 3）：
• 比較 1 和 2：次序正確，無須交換
• 比較 2 和 4：次序正確，無須交換
• 比較 4 和 5：次序正確，無須交換
第 3 輪結束：共進行了 0 次交換！演算法由此確定清單已經完全排序好。
重點摘要：冒泡排序法會比較相鄰成對的項目，並重複走訪清單，直到某一輪完全沒有發生任何交換為止。它編寫簡單，但處理大型清單時會變得非常緩慢且效率低下。
演算法 2：插入排序法（Insertion Sort）
插入排序法的運作方式，就跟很多人整理手上的撲克牌一模一樣。它透過每次從未排序部分提取一個項目，並將其「插入」到已排序部分的正確位置，逐項建立出排序好的清單。
插入排序法的運作步驟：
1. 在概念上將清單分為兩部分：左邊是已排序部分，右邊是未排序部分。
2. 一開始，第一個單獨的項目本身會被視為已排序。
3. 檢視未排序部分中的第一個項目。
4. 將它向後（向左）與已排序部分中的各個項目進行比較。
5. 將任何較大的項目向右平移（Shift）一個位置以騰出空間。
6. 將該項目插入（Insert）到正確的排序位置。
7. 重複這個過程，直到未排序部分沒有剩餘項目為止。
逐步追蹤範例（Tracing Insertion Sort）：
讓我們以升序排列這份清單：[6, 3, 7, 2]。
• 開始：已排序部分為 [6] | 未排序部分為 [3, 7, 2]
• 第 1 步：取出 3。與 6 比較。由於 \(3 < 6\)，將 6 向右平移並插入 3。
當前狀態：[3, 6 | 7, 2]
• 第 2 步：取出 7。與 6 比較。由於 \(7 > 6\)，它本來就在正確的位置。
當前狀態：[3, 6, 7 | 2]
• 第 3 步：取出 2。向後比較：\(2 < 7\)（平移 7）、\(2 < 6\)（平移 6）、\(2 < 3\)（平移 3）。將 2 插入到最開頭的位置。
最終排序狀態：[2, 3, 6, 7]
重點摘要：插入排序法會不斷從未排序部分取出下一個項目，透過平移較大的元素，將其插入到已排序部分的正確位置。它對於小型清單或原本就大致排序好的清單非常高效。
演算法 3：合併排序法（Merge Sort）
合併排序法是一種強大的演算法，它採用了分治法（Divide and Conquer）的策略。它並非一次過排序整份清單，而是將清單拆解成極小的部分，將各部分分別排序，最後再合併在一起。
合併排序法的運作步驟：
合併排序法主要分為兩個階段：
1. 分割（Divide）：不斷將未排序的清單一分為二，直到每個子清單剛好只包含一個元素為止。（根據定義，只包含單一項目的清單本身已經是排好序的！）。
2. 征服／合併（Conquer / Merge）：重複將相鄰成對的子清單按順序合併在一起。合併兩個子清單時，比較它們最前端的項目，把較小的一個放入新的合併清單中，重複此步驟，直到所有項目合併為一份完全排序好的清單。
逐步追蹤範例（Tracing Merge Sort）：
讓我們來排序這份清單：[8, 3, 5, 1]
第 1 階段：分割（Splitting）
• 將 [8, 3, 5, 1] 分成兩半：[8, 3] 和 [5, 1]
• 再次分割成獨立的單元素清單：[8]、[3]，以及 [5]、[1]
第 2 階段：合併（按順序合併）
• 合併 [8] 和 [3]：比較 8 和 3 \(\implies\) [3, 8]
• 合併 [5] 和 [1]：比較 5 和 1 \(\implies\) [1, 5]
• 合併 [3, 8] 和 [1, 5]：
- 比較最前端項目 3 和 1：1 較小 \(\implies\) 取出 1
- 比較最前端項目 3 和 5：3 較小 \(\implies\) 取出 3
- 比較最前端項目 8 和 5：5 較小 \(\implies\) 取出 5
- 取出最後剩餘的 8 \(\implies\) 取出 8
最終排序清單：[1, 3, 5, 8]
重點摘要：合併排序法會不斷分割清單，直到大小變為 \(1\)，然後按順序將它們重新合併。在處理大型數據集時，它比冒泡排序法或插入排序法快得多，但需要額外的記憶體來儲存各個子清單。
演算法實用性比較
根據課程指引，你需要運用邏輯推理來比較不同演算法在特定情境下的實用性。以下是各演算法的比較：
1. 冒泡排序法（Bubble Sort）：
• 運作方式：透過多輪走訪比較相鄰成對的項目。
• 最佳適用情境：小型清單，或用來檢查清單是否已經排序好。
• 主要限制：處理大量數據時速度非常慢且效率低下。
2. 插入排序法（Insertion Sort）：
• 運作方式：將項目逐一插入到持續增長的已排序部分中。
• 最佳適用情境：小型數據集，或將新項目加入到已排序好的清單中。
• 主要限制：處理大型、逆序或極度混亂的清單時效率不佳。
3. 合併排序法（Merge Sort）：
• 運作方式：分治法（先分割清單，再按順序合併）。
• 最佳適用情境：需要維持穩定、高速排序的大型數據集。
• 主要限制：在合併過程中需要額外的電腦記憶體來儲存所有被分割的子清單。
常見誤區與易犯錯誤
• 過早結束冒泡排序：請記住，僅僅到達清單末尾並不代表可以停下來。你必須在某一輪完整走訪中達到零次交換，才能證明清單已經完全排好。
• 誤以為分割就能完成排序：在合併排序法中，將清單一分為二並不會自動排序數字。真正的排序只發生在比較並組合數值的合併階段。
• 混淆平移（Shifting）與交換（Swapping）：插入排序法是將現有已排序的項目向右平移以騰出空位進行插入；它並不會像冒泡排序法那樣在整份清單中直接交換相鄰項目。
• 認定合併排序永遠是唯一最好的選擇：雖然合併排序法非常適合大型數據集，但對於極小的清單或大致已排好序的清單，像插入排序法這種較簡單的演算法可能更容易實踐，且佔用較少的運作記憶體。
快速複習總結
• 冒泡排序法：比較並排成對項目 \(\implies\) 次序錯誤即交換 \(\implies\) 當某一整輪為 0 次交換時停止。
• 插入排序法：分成已排序和未排序兩部分 \(\implies\) 挑選下一個未排序項目 \(\implies\) 平移較大項目 \(\implies\) 插入至合適位置。
• 合併排序法：重複分割至大小為 1 的子清單 \(\implies\) 按正確順序將子清單重新合併。