一次检查一个
线性搜索：逐个检查
想象你有 10 张卡片，编号 1 到 10，被随机打乱。
你想找到编号为 7 的卡片。
你从左到右依次翻开卡片，直到找到它。
| 场景 | 需要的翻卡数 |
|---|---|
| 最佳情况 | 1 次（幸运地第一次就对！） |
| 最坏情况 | 10 次（它是最后一张卡片） |
| 平均情况 | 大约 5 次 |
现在想象 100 张卡片。平均：大约 50 次翻卡。
1,000 张卡片？平均：大约 500 次翻卡。
看到规律了吗？卡片数量翻倍，工作量也翻倍。工作量增长是一条直线。
计算机科学家称这为 线性搜索 — 线性是指工作量像一条线一样增长：稳定 & 可预测。
线性搜索适用于任何列表，无论是否排序。这使它简单易用。但它可能会变慢。
有多少个名字？
你有一个班级名单，上面有 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]
显示每一遍后的列表。计算完成需要多少遍。