第一章 排序与搜索 (Sorting and Searching)
一、导读
1.1 本章学习目标
理解排序作为算法设计基础工具的核心地位，掌握不同排序算法的适用场景
掌握二分搜索算法的原理、实现及其变体形式
学会从实际问题中抽象出排序与搜索的模型，并选择最优解法
理解算法效率分析的基本方法，能够比较不同方案的时间与空间复杂度
掌握"分而治之"策略在排序与搜索问题中的具体应用
学会在实际工程约束（内存限制、数据规模）下做出合理的算法选择
理解数据组织方式对搜索效率的决定性影响
1.2 为什么本章如此重要
排序与搜索是计算机科学中最基本、最经典的问题之一。从早期的大型电话簿查找，到现代数据库索引、搜索引擎的底层实现，排序与搜索无处不在。Jon Bentley 在《编程珠玑》开篇就选择了这个主题，正是因为它们集中体现了算法设计的核心思想：如何将一个看似简单的问题，通过深入分析找到优雅而高效的解决方案。
在实际软件开发中，排序往往是许多复杂操作的前置步骤。一旦数据有序，搜索、去重、合并、统计等操作都会变得简单高效。Bentley 通过几个精心设计的例子展示了这一点：比如通过排序来检测重复的电话号码、通过排序来寻找最接近的点对、通过排序来解决集合交集问题。这些例子告诉我们，面对一个问题时，首先应该考虑是否可以将其转化为排序问题。
二分搜索虽然原理简单，但 Bentley 指出，大多数程序员在实现它时都会犯错误。这揭示了一个深刻的道理：看似简单的算法往往隐藏着微妙的边界条件。正确实现二分搜索需要对循环不变量、区间开闭、终止条件有精确的理解。这种对细节的严谨态度，是优秀程序员的基本素养。
本章还通过一些有趣的实例展示了算法选择的巨大影响。同一个问题，使用不同的算法可能导致数百万倍的性能差异。这种量级上的差异不是靠更快的硬件能够弥补的，而是需要从根本上理解算法的复杂度特性。对于任何需要处理大规模数据的系统来说，这种理解都是不可或缺的。
1.3 核心问题引导
给定一个包含 40 亿个随机排列的 32 位整数的文件，如何在不使用大量内存的情况下找到一个不在文件中的整数？
二分搜索的平均比较次数是多少？如何优化常数因子？
如何利用排序来高效地检测一组数据中的重复元素？
在内存不足以容纳全部数据的情况下，如何实现外部排序？
如何设计一个支持快速搜索的数据结构，同时兼顾插入和删除操作的效率？
排序算法的下界是什么？为什么基于比较的排序不可能突破 O(n log n)？
二、核心概念详解
2.1 二分搜索的深入剖析
二分搜索是计算机科学中最基本的算法之一，其基本思想是在有序数组中，每次将搜索范围缩小一半，直到找到目标元素或搜索范围为空。算法的时间复杂度为 O(log n)，对于十亿级别的数据量仅需约 30 次比较。
然而，Bentley 强调了一个令人惊讶的事实：尽管二分搜索的原理在 1946 年就被提出，但直到 1962 年才有人写出完全正确的实现。问题出在边界条件的处理上：中间点的计算 mid = (low + high) / 2 在某些情况下可能溢出；循环终止条件的选择（low <= high 还是 low < high）取决于具体需求；返回值的设计需要区分"找到"和"未找到"两种情况。
在实际工程中，二分搜索有许多重要的变体。例如，在有序数组中查找第一个等于目标值的元素（而非任意一个）、查找最后一个小于等于目标值的元素、查找目标值应该插入的位置等。每种变体都需要对标准的二分搜索框架进行微调，而这些微调往往容易引入 bug。理解循环不变量（loop invariant）是正确实现这些变体的关键：在每次迭代开始时，目标元素（如果存在）一定在当前搜索区间内。
2.2 排序作为问题求解工具
Bentley 通过多个例子展示了排序作为通用问题求解工具的强大能力。一个经典的例子是：给定两个包含大量电话号码的集合，如何高效地找出它们的交集？直接的两两比较需要 O(m × n) 的时间，而如果先对两个集合排序，然后使用双指针扫描，则总时间降为 O(m log m + n log n)。
另一个例子是寻找最接近的点对。给定平面上 n 个点，找到距离最近的两个点。暴力方法需要 O(n²) 的时间来检查所有点对。但如果按 x 坐标排序，可以利用一个关键观察：排序后，最近点对一定在相邻的若干对点中产生（具体证明需要更精细的分析）。这将问题从 O(n²) 降到了 O(n log n)。
排序还有一个重要的应用：检测数据中的重复元素。如果数据未排序，检测重复需要 O(n²) 的比较或使用额外的哈希表空间。而如果先排序，重复元素必然相邻，只需一次线性扫描即可检测完毕。Bentley 用这个例子来说明"先排序，后处理"的策略在许多场景下的有效性。
2.3 外部排序与大规模数据处理
当数据量大到无法全部放入内存时，内部排序算法（如快速排序、归并排序）就不再适用。这时需要使用外部排序（external sorting），其核心思想是：将数据分成若干块，每块分别排序后写回磁盘，然后通过多路归并得到最终的有序结果。
外部排序的分析需要考虑磁盘 I/O 的特性。与内存访问不同，磁盘的顺序读写速度远快于随机读写。因此，外部排序的设计目标是尽量减少随机 I/O 的次数，而充分利用顺序 I/O。归并排序天然适合这一要求：每一趟归并都是顺序读写，总 I/O 次数为 O(n log n) 次数据传送。
Bentley 还介绍了一种处理超大规模数据的巧妙方法：位图排序。如果需要在 32 位整数范围内排序和去重，且数据量不超过 2³²，可以使用一个位向量（bitmap）来表示所有可能的值。读入一个数就将对应位设为 1，最后扫描位向量输出所有为 1 的位置。这种方法只需要约 1.2 MB 的内存，却可以处理 40 亿个整数，空间效率极高。
2.4 算法复杂度的实际意义
理解算法复杂度不仅仅是理论分析的需要，更直接关系到程序的实际性能。Bentley 通过具体数字来说明不同复杂度量级的巨大差异：对于 n = 1,000,000 的数据，O(n) 算法需要约 1 秒，O(n log n) 需要约 20 秒，O(n²) 需要约 12 天，而 O(n³) 则需要约 32 年。这种量级上的差距远超过硬件速度的提升。
在实际选择算法时，还需要考虑常数因子。当数据量较小时，O(n²) 的插入排序可能比 O(n log n) 的快速排序更快，因为前者的常数因子更小、缓存命中率更高。许多高效的排序实现（如 C 标准库的 qsort）在递归到小规模子数组时会切换到插入排序，正是基于这一考虑。
另一个重要的实践原则是：在编写代码之前，先估算问题规模。如果数据量很小（比如 n < 100），那么使用简单算法即可；如果数据量很大（比如 n > 1,000,000），则必须选择高效算法。这种"先估算，后编码"的习惯可以帮助避免在性能上犯严重错误。
2.5 搜索树与平衡
当数据是动态变化的（需要频繁插入和删除），简单的有序数组就不够用了，因为数组的插入和删除操作需要 O(n) 的时间。这时需要使用搜索树（search tree）来组织数据。
二叉搜索树（BST）的基本性质是：对于树中每个节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。在平衡的 BST 中，搜索、插入和删除的时间复杂度都是 O(log n)。然而，在最坏情况下（如按有序序列插入），BST 可能退化为链表，搜索时间退化为 O(n)。
为了解决这个问题，研究者提出了多种平衡树方案，如 AVL 树、红黑树、B 树等。这些数据结构通过旋转或其他结构调整操作，在每次插入或删除后维护树的平衡性，从而保证 O(log n) 的最坏情况性能。Bentley 指出，选择哪种平衡方案取决于具体的应用场景：内存中的动态集合适合红黑树，磁盘上的索引结构适合 B 树。
三、深入分析与讨论
3.1 排序算法的选择策略
在实际工程中，没有一种排序算法在所有场景下都是最优的。选择排序算法需要综合考虑数据规模、数据分布、内存限制、稳定性要求等多个因素。
快速排序是通用排序的首选，其平均时间复杂度为 O(n log n)，常数因子较小，且具有良好的缓存局部性。但对于已经近乎有序的数据，快速排序可能退化为 O(n²)。此时，随机化选择主元（randomized pivot）或三数取中（median-of-three）等策略可以有效避免最坏情况。
归并排序的优势在于它是稳定排序（相等元素的相对顺序不变），且最坏情况也是 O(n log n)。它特别适合链表排序和外部排序，但在数组排序中需要额外的 O(n) 空间。堆排序的空间复杂度为 O(1)，且最坏情况也是 O(n log n)，但由于缓存不友好，实际速度通常不如快速排序。
对于小规模数据（n < 50），插入排序往往是最快的选择，因为它的简单性使得常数因子极小。对于几乎有序的数据，插入排序的时间接近 O(n)。许多标准库的排序实现采用混合策略：外层使用快速排序或归并排序，递归到小规模子问题时切换为插入排序。
3.2 搜索问题的空间-时间权衡
搜索问题的一个核心主题是空间与时间的权衡。最简单的搜索方法是线性搜索，时间复杂度 O(n)，不需要额外空间。如果允许预处理，可以先排序再二分搜索，预处理时间 O(n log n)，每次搜索时间 O(log n)。如果允许更多空间，可以使用哈希表实现 O(1) 的搜索时间，但需要 O(n) 的额外空间。
这种空间-时间权衡在实际系统设计中无处不在。数据库索引本质上就是一种空间换时间的策略：通过维护额外的索引结构，将查询时间从 O(n) 降低到 O(log n) 甚至 O(1)。缓存（cache）也是同样的思想：将频繁访问的数据放在更快的存储介质中，以空间换取访问速度。
Bentley 提醒我们，在做空间-时间权衡时，需要考虑问题的完整上下文：搜索的频率如何？数据是否会动态变化？可用的内存有多少？预处理的时间是否可以接受？只有综合考虑这些因素，才能做出合理的设计决策。
3.3 二分搜索的数学分析
对二分搜索进行精确的数学分析可以揭示一些有趣的性质。在成功搜索中（目标元素一定在数组中），平均比较次数约为 log₂n - 1。在失败搜索中（目标元素不在数组中），比较次数恰好为 ⌊log₂n⌋ + 1。
一个常被忽略的优化是：在二分搜索的每次迭代中，除了中间元素的比较外，还有两次边界比较（low <= high）。如果将这两个边界比较移到循环外部，通过设置"哨兵"元素来避免边界检查，可以减少每次迭代的比较次数。这种优化在早期的计算机上效果显著，在现代处理器上由于分支预测的改进，效果已经不那么明显。
另一个值得讨论的问题是：在什么情况下二分搜索不是最优的？如果搜索概率分布是已知的且高度不均匀，插值搜索（interpolation search）可以利用值的分布信息将平均搜索时间降低到 O(log log n)。但在均匀分布下，插值搜索的优势并不明显，且实现更复杂。
四、实践案例
4.1 电话号码去重问题
一个典型的实践案例来自电信行业：给定一个包含数百万个电话号码的文件，如何高效地去除重复号码？假设电话号码是 7 位数字（0 到 9,999,999），共有约一千万个可能的号码。
最直接的方案是使用哈希集合：逐个读入号码，如果不在集合中就加入并输出，否则跳过。这需要 O(n) 的时间和 O(n) 的额外空间。对于百万级别的号码，哈希表可能需要几十 MB 的内存。
更优雅的方案是使用位图排序：申请一个长度为 10,000,000 的位向量，初始全为 0。逐个读入号码，将对应位设为 1。最后扫描位向量，输出所有为 1 的位置。这种方法只需要约 1.2 MB 的内存，且时间复杂度为 O(n)，是空间效率和时间效率的完美结合。
如果内存限制更严格（比如只有几百 KB），可以采用多趟处理的方法：第一趟处理 0 到 999,999 的号码，第二趟处理 1,000,000 到 1,999,999 的号码，以此类推。每趟只需要一个小的位向量，代价是需要多次扫描输入文件。
4.2 海量日志文件的排序
一个实际的工程场景：一个 Web 服务器每天产生数十 GB 的访问日志，每行包含时间戳、IP 地址、请求 URL 等信息。需要按时间戳排序这些日志，以便进行后续分析。
由于日志文件远大于可用内存，必须使用外部排序。具体步骤如下：首先，将大文件分成若干小块（每块大小约为可用内存的一半），每块使用快速排序在内存中排序后写回临时文件。然后，对所有临时文件进行 K 路归并：维护一个大小为 K 的最小堆，每次取出最小元素写入输出文件，并从对应的临时文件中读入下一个元素。
这种外部排序方案的时间复杂度为 O(N log N)，其中 N 是总记录数。I/O 次数为 O(N log(N/M))，其中 M 是每次可以处理的块大小。对于 50 GB 的日志文件和 1 GB 的可用内存，大约需要 6 趟处理，总 I/O 量约为 300 GB（顺序读写），在现代磁盘上约需几分钟即可完成。
五、常见误区与注意事项
5.1 二分搜索的边界错误
最常见的错误是循环边界条件写错。使用 while (low <= high) 还是 while (low < high) 取决于具体需求：前者在循环结束时 low > high，表示搜索范围为空；后者在循环结束时 low == high，还需要额外判断。混淆这两种模式是 bug 的主要来源。
5.2 中间点计算的溢出问题
mid = (low + high) / 2 在 low + high 超过整数最大值时会溢出。正确的写法是 mid = low + (high - low) / 2，或者使用无符号右移 mid = (low + high) >>> 1（Java）。这个 bug 在许多标准库中都曾出现过。
5.3 忽视数据规模的影响
许多程序员在编写代码时不考虑数据规模，总是使用同一套算法。当数据量从百级增长到百万级时，O(n²) 的算法可能从毫秒级退化到天级。养成在编码前估算数据规模和算法复杂度的习惯，可以避免许多性能问题。
5.4 过度依赖标准库排序
标准库的排序函数（如 C 的 qsort、C++ 的 std::sort、Python 的 sorted）通常是高度优化的通用排序。但在某些特殊场景下，自定义排序可能更高效：例如，数据几乎有序时可以使用插入排序、数据范围有限时可以使用计数排序、需要稳定排序时应确认库函数是否保证稳定性。
5.5 忽视缓存局部性
算法复杂度分析通常忽略常数因子，但在实际运行中，缓存局部性对性能的影响可能达到数倍。快速排序之所以在实践中通常优于堆排序，很大程度上是因为它的内层循环具有良好的空间局部性，能够充分利用 CPU 缓存。
六、本章小结
本章围绕排序与搜索这两个经典问题，展示了算法设计的核心思想。二分搜索虽然原理简单，但正确实现需要对边界条件有精确的掌控。排序不仅是基本操作，更是一种强大的问题求解工具：许多看似与排序无关的问题，通过排序可以大幅简化。在处理大规模数据时，外部排序和位图技术等方案展示了如何在内存限制下高效工作。算法选择的关键在于理解问题的规模、数据的特性以及可用的资源，在时间和空间之间做出合理的权衡。
七、思考题与练习
实现一个二分搜索函数，返回目标值在有序数组中第一次出现的位置。如果不存在，返回应该插入的位置。
给定一个包含 n 个整数的数组，其中某些整数出现了奇数次，其余出现了偶数次。设计一个 O(n log n) 时间的算法找出所有出现奇数次的整数。
假设你有一个 40 亿个 32 位整数的文件，但只有几百 KB 的内存。设计一个算法找到一个不在文件中的整数。如果内存只有几百字节呢？
比较快速排序和归并排序在不同数据分布下的表现：完全随机、近乎有序、大量重复、逆序。用实验验证你的分析。
设计一个算法，在 O(n log n) 时间内找到一个数组中的"主导元素"（出现次数超过 n/2 的元素）。
给定两个已排序的数组，大小分别为 m 和 n（m << n），设计一个比先合并再排序更高效的算法来合并它们。
实现一个外部排序算法，处理一个 10 GB 的文件，每次只能使用 256 MB 内存。分析你的算法的 I/O 次数。
证明：基于比较的排序算法在最坏情况下至少需要 Ω(n log n) 次比较。