搜索与排序算法

欢迎来到算法的世界！在本章中，我们将探讨计算机用来寻找信息并将其排列顺序的“食谱”。无论是你手机里的联系人搜索，还是将 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)
说明：将列表拆分后再按顺序合并。
效率：非常高

最后提醒：考试时，你可能会看到几行程序代码或伪代码，并被问到“这是哪种算法？”
- 寻找交换相邻元素的特征（冒泡排序）。
- 寻找寻找中间点的特征（二分搜索）。
- 寻找将列表对半拆分的特征（合并排序）。

你一定做得到的！通过在纸上用一组小数字练习追踪这些算法，继续保持练习。