逐一檢查
線性搜尋：逐一檢查
想像你有 10 張面朝下的卡片，編號 1 到 10，隨機打亂順序。
你想找編號為 7 的卡片。
你從左到右逐張翻卡片，直到找到它。
| 情境 | 需要翻牌次數 |
|---|---|
| 最佳情況 | 1 次翻牌（幸運的第一次！） |
| 最差情況 | 10 次翻牌（它在最後一張卡片） |
| 平均 | 約 5 次翻牌 |
現在想像 100 張卡片。平均：約 50 次翻牌。
1,000 張卡片？平均：約 500 次翻牌。
看出規律了嗎？卡片翻倍，工作量翻倍。工作量以直線增長。
電腦科學家稱這為 線性搜尋 — linear 意味著工作量像一條線一樣增長：穩定且可預測。
線性搜尋適用於任何清單，無論是否排序。這使它很簡單。但它可能會變慢。
有多少個名字？
你有一份 20 個名字 的班級名單，寫成隨機順序。
你需要找到名字 Zoe。
你從清單的頂端開始，逐個檢查名字。
將清單分成兩半
二分搜尋：跳到中間
二分搜尋有一個規則：清單必須先排序。
如果你的 20 個名字清單從 A 到 Z 排序，你可以使用二分搜尋。
它是如何工作的： 打開中間的名字（名字 #10）。問：Zoe 在這個名字之前還是之後？
Z 在字母表的末尾附近，所以 Zoe 在中間之後。丟棄前半部分。現在你只剩下名字 11-20。
檢查那 10 個名字的中間（名字 #15）。Z 在 M 之後，所以 Zoe 在名字 #15 之後。丟棄名字 11-14。現在你有名字 16-20。
持續對半切割。每次檢查都會移除剩餘名字的一半。
| 清單大小 | 二分搜尋的最多檢查次數 |
|---|---|
| 20 個名字 | 最多 5 次檢查 |
| 1,000 個名字 | 最多 10 次檢查 |
| 1,000,000 個名字 | 最多 20 次檢查 |
將其與線性搜尋在 1,000,000 個名字上進行比較：平均 500,000 次檢查。
二分搜尋每次將清單切成一半。反覆對半切割會非常快速達到 1 — 這就是它保持如此快速的原因。
在排序的清單中找到 'fig'
這是一份 8 個字詞的排序清單：
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
你想使用二分搜尋找到 fig。
記住：檢查中間，詢問你的目標是在之前還是之後，然後將清單對半切割。
將相鄰項目交換至順序
冒泡排序：比較相鄰項目並交換
冒泡排序通過一次比較兩個相鄰項目來將清單排序。
如果兩個相鄰項目順序錯誤 — 交換它們。
持續遍歷清單，直到沒有什麼需要交換。
例子：排序 [5, 3, 8, 1]
遍歷 1：
- 比較 5 & 3。5 > 3，所以交換 → [3, 5, 8, 1]
- 比較 5 & 8。5 < 8，不交換 → [3, 5, 8, 1]
- 比較 8 & 1。8 > 1，所以交換 → [3, 5, 1, 8]
遍歷 2：
- 比較 3 & 5。OK → [3, 5, 1, 8]
- 比較 5 & 1。5 > 1，交換 → [3, 1, 5, 8]
- 比較 5 & 8。OK → [3, 1, 5, 8]
遍歷 3：
- 比較 3 & 1。3 > 1，交換 → [1, 3, 5, 8]
- 比較 3 & 5。OK。比較 5 & 8。OK。
完成！[1, 3, 5, 8] ✓
注意：最大的數字在每次遍歷時 冒泡 到清單的末尾。這就是冒泡排序名字的由來。
冒泡排序有效。它對於大清單來說不是最快的，但很容易理解 — 非常適合學習。
用冒泡排序排序 [4, 2, 7, 1]
使用冒泡排序排序此清單：[4, 2, 7, 1]
顯示每次遍歷後的清單。計算完成需要多少次遍歷。