第五章 排序与查找心法

第五章 · 排序与查找心法

本章要回答的三个问题：把一堆乱序数据变有序，为什么"交换简单的招式"与"分治的招式"效率差出数量级？比较排序是不是快到头了、突破又靠什么？数据一旦有序，查找能便宜到什么程度？

为什么会有这一章

排序是计算机科学的"国民课题"：数据库的索引、推荐的召回、去重与合并、报表输出，背后全是排序。它也是最好的复杂度教具——同一目标，冒泡、插入、快排、堆排、计数排序给出从平方级到线性级的完整谱系，每一步差距都能用操作计数说清。查找则是排序的孪生兄弟：无序只能扫，有序可以砍半，二分查找用"每次排除一半"把查找压到对数级，是全书性价比最高的一招。两兄弟合起来还有一个隐藏主题：预处理换查询——排一次序，此后每次查找都沾光，这笔账怎么算，本章会给出公式化的答案。

本章按"功力进阶"排布：入门三式（冒泡、选择、插入）胜在简单与稳定，练手也练分析；分治双雄（快排、归并）与堆排序代表比较排序的主流战力；非比较排序（计数、基数）绕开比较下界，在特定数据分布下打出线性；最后收束到查找——线性扫与二分砍半的对照，以及二分思想的变形。

排序还是"稳定与否、原地与否"这两个工程维度的最佳教材：同样能排好序的算法，在多关键字排序、内存受限场景下的高下立判。本章每节都会把这两栏标出来，读完你应当能按"数据规模、是否近有序、内存预算、稳定性要求"四问给真实需求开出排序处方。

读完能解决什么

对照开头的问题，本章的知识点清单如下：

• 能手写冒泡、选择、插入三式，数出各自的比较与搬移次数，并说出插入排序"近有序时近线性"的原因；
• 能陈述稳定性的定义，判断给定排序是否稳定，并说出稳定性在多关键字排序里的价值；
• 能跟踪 Lomuto 分区的一次完整过程，解释快排最优 O(n log n) 与最坏 O(n²) 的来源及随机化轴点的意义；
• 能手写归并排序的合并过程，说明它稳定但费空间；能复述比较排序的 n log n 下界直觉；
• 能实现堆排序（原地、不稳定）并解释"建堆线性、排序 n log n"；
• 能说明计数排序对数据分布的要求（键为小范围整数）及其线性时间的来历；
• 能手写二分查找与左边界变体，说出循环不变量与中点溢出的坑。

各节怎么分工

先决条件

• 第一章复杂度推导（对数级来自每层减半）与递归（快排、归并的骨架）；
• 第二章数组（搬移计数）与 3.4 节堆（堆排序的地基）；
• 无需第三章 BST 知识，但读过会更容易理解"比较树"的下界论证。

往下走到哪

排序与查找是前面所有结构的一次大阅兵：数组是战场、递归是骨架、堆是引擎。本章出口直通两处：第六章的分治法与动态规划大量复用本章的"分而治之、预处理换查询"心法；第七章字符串匹配则把"查找"推进到模式串层面。工程上，语言内置排序（TimSort、pdqsort）正是本章各招式的工业化混编，读完你能看懂它们为什么那样设计。检验掌握程度的方式带着纸笔做：任选一章的排序，对同一组八个数写出每趟结束后的数组状态——写得出中间态，才是真会，只背得出复杂度不算。

排序与查找的知识谱系