逐一检查
线性搜索:逐一检查
假设你有一堆10张面朝下排列的扑克牌,编号从1到10,已经随机排列。
你想找到编号为 7 的那张牌。
你从左到右逐张翻牌,直到找到它。
| 场景 | 需要翻的次数 |
|----------|-------------|
| 最佳情况 | 1次翻牌(运气很好,第一次就找到了!) |
| 最坏情况 | 10次翻牌(它是最后一张牌) |
| 平均情况 | 大约5次翻牌 |
现在假设有100张牌。平均情况大约是 50次翻牌。
1000张牌?平均情况大约是 500次翻牌。
你能看到模式了吗?将牌数翻倍,工作量也会翻倍。工作量会按直线增长。
计算机科学家称之为 线性搜索 —— 线性意味着工作量会按直线增长:稳定且可预测。
线性搜索可以在任何列表上工作,无论是否有序。这使得它简单。但是,它可能会很慢。
有多少名字?
你有一份包含 20个名字 的班级名单,名字是随机排列的。
你需要找到名字为 Zoe。
你从名单的顶部开始,逐个检查名字。
将列表减少一半
二分搜索:跳到中间
二分搜索有一条规则: 列表必须先排序。
如果你的20个名字从A到Z排序,你可以使用二分搜索。
它是如何工作的: 打开中间的名字(name #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'
以下是一个已排序的列表:
1. 苹果 2. 香蕉 3. 樱桃 4. 草莓 5. 黑莓 6. fig 7. 草莓 8. 草莓
你想使用二分搜索来找到 fig。
记住:检查中间,问你的目标是否在前面或后面,然后将列表分成两半。
交换相邻元素以排序
冒泡排序:比较相邻元素并交换
泡沫排序通过比较两个邻近元素来对列表进行排序。
如果两个邻近的元素不符合顺序 — 交换它们。
在列表中不断通过直到不再需要交换为止。
示例：对 [5, 3, 8, 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]
第二轮:
- 比较 3 和 5。OK → [3, 5, 1, 8]
- 比较 5 和 1。5 大于 1，交换 → [3, 1, 5, 8]
- 比较 5 和 8。OK → [3, 1, 5, 8]
第三轮:
- 比较 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]
显示每次遍历后的列表。计算完成排序所需的遍历次数。