欢迎来到搜索与排序的世界！
你有没有想过，Google 如何在几毫秒内从数十亿个网页中找到特定结果？或者，当你在手机通讯录新增一个名字时，它又是如何瞬间自动完成字母排序的？这就是搜索与排序算法 (Searching and Sorting Algorithms) 的威力。在本章中，我们将学习计算机如何有效率地组织数据并找到所需的信息。别担心步骤看起来很多——只要把它们想象成处理数据的“食谱”。一旦你掌握了这些“食材”，所有的步骤都会变得非常合情合理！
1. 搜索算法
搜索是指在数据集合中找到特定项目（称为目标值，target）的过程。在课程大纲中，我们主要聚焦于两种方法：线性搜索 (Linear Search) 与 二分搜索 (Binary Search)。
线性搜索 (Linear Search)
这是寻找目标最直接的方法。你从列表的最开头开始，逐一检查每一个项目，直到找到目标或者到达列表末端为止。
生活类比： 想象你在电影院的一排座位中找朋友。你从 1 号位开始，盯着每个人的脸看，直到看到你的朋友为止。
运作方式（步骤说明）：
1. 从第一个元素（索引值 0）开始。
2. 将当前元素与目标值进行比较。
3. 如果两者相符，恭喜你！你找到了。
4. 如果不符，移动到下一个元素。
5. 重复以上动作，直到找到目标或遍历完所有项目。
快速复习： 线性搜索适用于任何列表，无论该列表是否有经过排序！
二分搜索 (Binary Search)
二分搜索的速度快得多，但它有一条严格的规定：列表必须先经过排序！ 它采用的是“分治法 (divide and conquer)”策略。
生活类比： 试想一本实体字典。如果你要查 "Marmalade"，你绝对不会从第 1 页开始翻。你会直接翻到中间，如果你看到 "P"，你就知道 "M" 一定在前半部。你在一秒钟内就排除了整本字典的一半内容！
运作方式（步骤说明）：
1. 找出当前列表的中间元素。
2. 如果中间元素就是目标值，搜索结束！
3. 如果目标值小于中间值，舍弃右半部，在左半部重复搜索。
4. 如果目标值大于中间值，舍弃左半部，在右半部重复搜索。
5. 持续进行分割，直到找到目标项目，或是该“半部”范围变为空为止。
常见错误： 在建议使用二分搜索前，忘了检查列表是否已排序。如果列表是无序的，二分搜索将会失效！
重点总结： 对于小型或未排序的列表，使用线性搜索；对于大型且已排序的列表，请务必使用二分搜索以节省时间。
2. 排序算法
排序是指将数据按特定顺序（如字母顺序或数字大小）排列的过程。我们将探讨四种不同的排序“食谱”。
冒泡排序 (Bubble Sort)
在冒泡排序中，最大的数值会通过重复的交换过程，像气泡一样逐渐“浮”到列表的末端。
过程： 比较两个相邻的项目。如果顺序不对，就交换它们。对整个列表反复进行此动作，直到不需要再进行交换为止。
你知道吗？ 冒泡排序通常被认为是最容易编写的算法，但在处理大量数据时，它的速度也是最慢的之一。
插入排序 (Insertion Sort)
插入排序是一次一个地建立已排序的列表。它会选取一个未排序的项目，并将其“插入”到已排序项目中的正确位置。
生活类比： 想象你在整理一副扑克牌。你一次拿起一张牌，然后将它滑入手中有牌组的正确位置。
运作方式： 从第二个项目开始。将其与左边的项目进行比较。持续向左移动，直到它遇到比自己小的项目或是到达列表开头为止。
合并排序 (Merge Sort)
合并排序是一种递归 (recursive) 算法，它遵循“分治法 (Divide and Conquer)”原则。
运作方式：
1. 分割 (Divide)： 反复将列表对半分，直到每个子列表只剩下 1 个项目。
2. 征服 (Conquer)： 只有 1 个项目的列表预设为“已排序”。
3. 合并 (Combine)： 将这些小列表按正确顺序合并回去，直到恢复成一个完整的已排序大列表。
快速排序 (Quicksort)
快速排序同样使用“分治法”，但它聚焦于一个基准值 (pivot)。
运作方式：
1. 选择一个项目作为基准值（通常选第一个或最后一个）。
2. 分割 (Partitioning)： 将所有比基准值小的项目移到左边，比基准值大的移到右边。
3. 此时，基准值已处于最终且正确的位置！
4. 对左右两边重复上述过程，直到整个列表完成排序。
重点总结： 冒泡与插入排序简单但处理巨量数据时很慢。合并排序与快速排序较复杂，但在处理大型列表时，因其较优异的效率而更受欢迎。
3. 算法效率（Big-O 符号）
我们该如何比较算法的好坏？我们会使用 Big-O 符号 (Big-O Notation)。它衡量的是最差情况的时间复杂度 (worst-case time complexity)——简单来说，当数据量 (\(n\)) 增加时，算法所需的时间会增加多少？
“速度”等级（由快到慢）：
• \(O(1)\) - 常数时间： 无论 \(n\) 的大小如何，耗时始终相同。
• \(O(\log n)\) - 对数时间： 非常快！随着 \(n\) 的增加，时间增长缓慢（例如：二分搜索）。
• \(O(n)\) - 线性时间： 时间随着数据量等比例增长（例如：线性搜索）。
• \(O(n \log n)\) - 线性对数时间： 对于排序而言相当有效率（例如：合并排序）。
• \(O(n^2)\) - 平方时间： 处理大量数据时很慢。如果将数据量加倍，所需时间会变成原来的四倍（例如：冒泡排序）。
最差情况复杂度比较表：
线性搜索： \(O(n)\)
二分搜索： \(O(\log n)\)
冒泡排序： \(O(n^2)\)
插入排序： \(O(n^2)\)
快速排序： \(O(n^2)\)（注：这是当每次选择的基准值都很差时会发生的情况！）
合并排序： \(O(n \log n)\)
记忆小贴士： 把 Big-O 想象成一种“保证”。如果一个算法是 \(O(n)\)，计算机保证在最糟糕的情况下，其执行时间也不会超过与数据量成线性关系的时间。
快速复习箱：
• 搜索： 二分搜索比线性搜索快，但需要数据已排序。
• 排序： 在最差情况下，合并排序通常是最稳定的速度选择 (\(O(n \log n)\))。
• 复杂度： \(O()\) 括号里面的值越小，代表算法越好、越快！
总结
搜索与排序是高效程序设计的基石。线性搜索是你的“逐一检查”工具，而二分搜索则是你的“对半拆解”工具。在排序方面，冒泡排序和插入排序非常适合作为学习基础与处理小型列表，但合并排序与快速排序因其更佳的 Big-O 效能，成为实际软件开发中的主力。继续练习这些步骤，你很快就会成为算法专家！