搜尋與排序演算法
歡迎來到演算法的世界！在本章中，我們將探討電腦用來尋找資訊並將其排列順序的「食譜」。無論是你手機裡的聯絡人搜尋，還是將 Spotify 播放清單按藝人分類，這些演算法都在背後默默運作。
如果一開始覺得有點難也不用擔心；我們會把每個處理過程拆解成簡單易懂的小步驟！
事前檢查：在我們開始之前，請記住列表 (List)（或稱陣列 Array）只是一組儲存在一起的資料項目，就像學校走廊上一排置物櫃一樣。
第一節：搜尋演算法
搜尋就是要在資料列表中找到特定的項目（即目標 Target）。
1. 線性搜尋 (Linear Search)
線性搜尋是尋找目標最簡單的方法。它從列表的最開頭開始，逐一檢查每一個項目，直到找到目標或到達列表末端為止。
類比：想像你在凌亂的抽屜裡找一隻特定的綠色襪子。你拿起第一隻檢查，然後是第二隻、第三隻，直到你找到那隻綠色的為止。
運作方式（步驟拆解）：
1. 從列表的第一個項目開始。
2. 將此項目與你正在尋找的目標值進行比較。
3. 如果兩者相符，恭喜！你找到了。
4. 如果不符，移動到列表中的下一個項目。
5. 重複步驟 2-4，直到找到項目或到達列表末端。
重點複習：
- 前置要求：無！列表可以是任何順序（未經排序）。
- 最適合：小型列表。
- 缺點：對於大型列表來說非常慢，因為你可能需要檢查每一個項目。
2. 二元搜尋 (Binary Search)
二元搜尋比線性搜尋快得多，也更「聰明」，但它有一個非常重要的規則：開始前，列表必須已經排序（例如按字母順序或數字大小）。
類比：想像一本實體字典。你不會從第 1 頁開始翻找 "Zebra" 這個字。你會直接跳到中間，發現中間是「M」，意識到「Z」在後面，於是完全忽略掉字典的前半部分！
運作方式（步驟拆解）：
1. 找到已排序列表的中間項目。
2. 將中間項目與你的目標值進行比較。
3. 如果中間項目就是目標，任務完成！
4. 如果目標小於中間項目，捨棄列表的右半部分。
5. 如果目標大於中間項目，捨棄列表的左半部分。
6. 對剩下的半部分重複上述過程，直到找到項目為止。
為了找到中間位置，電腦通常使用這個公式：
\( middle = (first + last) / 2 \)
常見錯誤：許多學生會忘記二元搜尋只適用於已排序列表。如果列表亂七八糟的，二元搜尋就會失敗！
你知道嗎？如果你有 1,000,000 個項目的列表，線性搜尋可能需要 1,000,000 個步驟，但二元搜尋只需要約 20 個步驟！這就是「分治法 (Divide and Conquer)」的力量。
關鍵結論：列表雜亂且少量時使用線性搜尋；列表有序且龐大時使用二元搜尋。
第二節：排序演算法
排序是指將資料按特定順序排列（通常是遞增排序 Ascending，如 1 到 10 或 A 到 Z）。
1. 氣泡排序 (Bubble Sort)
氣泡排序是一種簡單的演算法，它會遍歷列表，比較相鄰的對，如果順序錯誤就交換它們。最大的數值會像「氣泡」一樣浮動到列表的末端。
運作方式（步驟拆解）：
1. 觀察列表中的前兩個項目。
2. 如果第一個比第二個大，就交換它們。
3. 移動到下一對（第 2 和第 3 個項目），重複比較與交換的過程。
4. 持續進行直到到達列表末端（這稱為一次遍歷 Pass）。
5. 重複整個過程，直到某一次遍歷過程中完全沒有發生交換為止。
重點複習：
- 優點：程式碼編寫非常簡單。
- 缺點：對於大型列表來說非常慢且效率低。
2. 插入排序 (Insertion Sort)
插入排序每次只排序一個項目來建立已排序的列表。它從「未排序」的部分取出每個項目，並將其插入到「已排序」部分的正確位置。
類比：想像你在玩紙牌遊戲。你一次拿一張牌，然後把它插入到手中的正確位置，這樣你的牌始終都是有序的。
運作方式（步驟拆解）：
1. 從列表中的第二個項目開始（假設第一個項目已經是一個「已排序列表」）。
2. 將它與左邊的項目進行比較。
3. 將其插入到正確的位置，使左側的項目保持有序。
4. 移動到下一個項目並重複上述步驟，直到所有項目都處理完畢。
記憶小撇步：聯想一下將書本「插入」書架，或將牌「插入」手中的過程。
3. 合併排序 (Merge Sort)
合併排序是一種分治法 (Divide and Conquer) 演算法。它比較複雜，但在處理大量資料時速度快得多。
運作方式（步驟拆解）：
1. 分割 (Divide)：將列表反覆對半拆分，直到每個項目都成為一個只含一個元素的微小列表。
2. 征服 (Conquer)：將這些微小列表兩兩合併回一起。在合併的同時，將項目按正確順序排列。
3. 重複合併過程，直到最後組合成一個單一、完全排序的列表。
類比：如果你需要整理 100 份文件，你可以把 50 份給朋友，另外 50 份給另一個朋友。他們各自整理好後，你再透過比較每堆最上面的文件，將它們「合併」在一起。
關鍵結論：
- 氣泡排序：慢，透過交換相鄰元素進行。
- 插入排序：較適合小型列表，將元素滑入正確位置。
- 合併排序：在大數據集下非常快，運用「分治法」。
第三節：摘要表格
利用此表格快速比較各演算法，幫助考試複習！
演算法：線性搜尋 (Linear Search)
是否需要已排序列表？否
效率：低
演算法：二元搜尋 (Binary Search)
是否需要已排序列表？是
效率：高
演算法：氣泡排序 (Bubble Sort)
說明：透過交換相鄰元素直到排序完成。
效率：低
演算法：插入排序 (Insertion Sort)
說明：將項目逐一放置到正確位置。
效率：中
演算法：合併排序 (Merge Sort)
說明：將列表拆分後再按順序合併。
效率：非常高
最後提醒：考試時，你可能會看到幾行程式碼或偽代碼，並被問到「這是哪種演算法？」
- 找尋交換相鄰元素的特徵（氣泡排序）。
- 找尋尋找中間點的特徵（二元搜尋）。
- 找尋將列表對半拆分的特徵（合併排序）。
你一定做得到的！透過在紙上用一小組數字練習追蹤這些演算法，繼續保持練習。