深色模式
05 · 排序与二分
排序是"预处理"，二分是"利用有序"。这两个是手写代码的高频考点，边界写错就直接挂。
一句话本质
- 排序：把无序变有序，代价 O(n log n)——这是基于比较的排序的理论下界。
- 二分：有序之后，每次砍一半，O(log n) 找到目标。
生活类比
| 算法 | 场景 |
|---|---|
| 快排 | 抽一个人当"基准"，比他矮的站左边，高的站右边，然后左右各自再排 |
| 归并 | 两队已经排好的人，各看队首，谁矮谁先出列（合并） |
| 堆排 | 反复从"最值堆"里取最大值 |
| 插入排序 | 打扑克理牌：新牌插到合适的位置 |
| 二分 | 查字典：翻到中间，比要找的字大就往前翻一半 |
核心机制
一、三种 O(n log n) 排序的对比
| 快排 | 归并 | 堆排 | |
|---|---|---|---|
| 平均 | O(n log n) | O(n log n) | O(n log n) |
| 最坏 | O(n²) | O(n log n) | O(n log n) |
| 空间 | O(log n)（递归栈） | O(n)（辅助数组） | O(1) |
| 稳定性 | 不稳定 | 稳定 | 不稳定 |
| 缓存友好 | 好 | 一般 | 差（跳跃访问） |
| 实际速度 | 最快 | 中等 | 较慢 |
为什么快排实际最快：虽然三者复杂度相同，但快排是原地 + 顺序访问，缓存命中率高，常数最小。
二、快排：为什么最坏是 O(n²)，怎么避免
分区（partition）：
选一个 pivot
把小于它的放左边，大于它的放右边
返回 pivot 的最终位置
然后递归左右两半。最坏情况：每次选的 pivot 都是最大或最小值 > 分区后一边为空、一边是 n-1 个 > 递归深度 n > O(n²)。
什么时候会这样：数组已经有序或逆序，而你固定选第一个/最后一个元素当 pivot。这是最坑的地方——"已经排好序的数组"反而最慢。
三种避免方式：
- 随机选 pivot：期望 O(n log n)，实现简单。
- 三数取中：取首、中、尾三个数的中位数当 pivot。
- 三路快排：分成
<pivot、=pivot、>pivot三段，大量重复元素时性能极好（这是工程上最实用的优化）。
递归深度：最坏 O(n)，会爆栈。优化：先递归较短的一边，较长的一边用循环（尾递归优化），深度降到 O(log n)。
三、归并：稳定 + 可外部排序
分：把数组对半分，递归排序左右
合：两个有序数组合并成一个（双指针，谁小取谁）为什么稳定：合并时，相等元素取左边的，所以左边（原本在前）的仍在前面。
代价：需要 O(n) 辅助空间。这是它不如快排常用的主要原因。
杀手级应用：外部排序。数据大到内存装不下时：
- 分块读入内存，每块排序后写回磁盘（得到若干有序小文件）。
- 多路归并这些小文件（用最小堆选当前最小的）。
这就是数据库 ORDER BY 超出内存时的做法，也是大数据排序的基础。
四、稳定性：什么场景真的需要
稳定 = 相等元素的相对顺序不变。
什么时候需要：多关键字排序。
先按"年龄"排序，再按"姓名"排序
如果第二次排序是稳定的 > 同名的人之间仍按年龄有序
如果不稳定 > 年龄信息被打乱，白排了稳定排序：冒泡、插入、归并、计数、基数 不稳定排序：选择、快排、堆排、希尔
五、二分的两种写法（这是最容易错的地方）
写法 A：闭区间 [left, right]
java
int binarySearch(int[] a, int target) {
int left = 0, right = a.length - 1; // 闭区间
while (left <= right) { // <= 因为区间非空
int mid = left + (right - left) / 2; // 防溢出
if (a[mid] == target) return mid;
else if (a[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}写法 B：左闭右开 [left, right)
java
int binarySearch(int[] a, int target) {
int left = 0, right = a.length; // 右开
while (left < right) { // < 因为区间是 [left, right)
int mid = left + (right - left) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) left = mid + 1;
else right = mid; // 不是 mid-1
}
return -1;
}两种写法不能混。混了就是经典 bug：while (left < right) 配 right = mid - 1 会漏元素。
mid = left + (right - left) / 2 而不是 (left + right) / 2：防止 left + right 溢出 int。
六、二分的变形：找边界
找第一个 >= target 的位置（左边界）：
while (left < right) {
mid = left + (right - left) / 2;
if (a[mid] < target) left = mid + 1;
else right = mid; // 不排除 mid
}
return left; // 可能是 a.length（不存在）
找最后一个 <= target 的位置（右边界）：
while (left < right) {
mid = left + (right - left + 1) / 2; // 注意 +1，向上取整
if (a[mid] <= target) left = mid;
else right = mid - 1;
}
return left;右边界为什么要 +1 向上取整：如果 left 和 right 相邻（right = left + 1），mid 会算成 left，然后 left = mid 就死循环了。加 1 让 mid 取到 right，才能推进。
这是二分最容易挂的地方，必须记住。
七、工程里实际用的排序
没有一个排序在所有场景最优，所以标准库都是混合策略：
Java 的 Arrays.sort：
基本类型 > 双轴快排（DualPivotQuicksort，不稳定）
对象类型 > TimSort（归并 + 插入，稳定）
为什么不同：基本类型不需要稳定性，快排更快；对象类型可能要稳定
C++ 的 std::sort：
Introsort = 快排 + 堆排 + 插入排序
快排递归太深（超过 2log n）就切换成堆排，保证最坏 O(n log n)
小数组（<16）用插入排序（常数小）
Python 的 sorted：Timsort（归并 + 插入，稳定，利用数据中已有的有序片段）Introsort 的思路值得记住：用快排的常数优势 + 堆排的最坏情况保证 + 插入排序的小数组优势，三者结合。这是"工程实用主义"的典范。
为什么这么设计
反事实 1：为什么基于比较的排序下界是 O(n log n)
n 个元素有 n! 种排列，每次比较只能得到"是/否"两种结果。要区分 n! 种情况，至少需要 log₂(n!) 次比较。而 log₂(n!) ≈ n log n（斯特林公式）。
所以 O(n log n) 是理论下界，不可能更快（基于比较）。想更快只能用非比较排序（计数、基数、桶排序），它们利用"数据本身的特性"（比如范围有限），代价是适用场景受限。
反事实 2：如果二分不要求有序
那就只能线性扫描 O(n)。有序是二分的唯一前提，也是它 O(log n) 的唯一来源。
推论：如果数据会频繁变动（增删），维护有序的代价可能超过二分的收益——这时用哈希表（O(1) 查找，但无序）或平衡树（O(log n) 增删查，且有序）更合适。
反事实 3：如果快排不做随机化
面对"已排序"的输入直接退化成 O(n²)。而现实中的数据经常是部分有序的（日志按时间、ID 递增），所以随机化/三数取中不是可选优化，是必需的。
面试怎么问
Q：快排的思路？为什么最坏 O(n²)？怎么优化？
分区 + 递归。最坏是每次 pivot 都是极值，分区极不均衡，递归深度 n。 优化：随机 pivot、三数取中、三路快排（重复元素多时）、小区间用插入排序。
Q：归并和快排的区别？
快排：原地、不稳定、平均快、最坏 O(n²)；归并：需 O(n) 空间、稳定、最坏也是 O(n log n)、适合外部排序和链表排序。
Q：什么是稳定排序？哪些是稳定的？
相等元素相对顺序不变。稳定的：冒泡、插入、归并、计数、基数。不稳定的：选择、快排、堆排、希尔。
Q：二分查找的边界怎么写？
关键是区间定义要一致：闭区间
[l,r]配while(l<=r)和r=mid-1；左闭右开[l,r)配while(l<r)和r=mid。不能混。
Q：手写一个"找第一个大于等于 target 的位置"。
用左闭右开写法，
a[mid] < target时l = mid+1，否则r = mid，最后返回l。 注意：返回值可能等于数组长度（表示都比 target 小），要处理。
追问链：
快排为什么平均 O(n log n)？（每次分区大致均分，递归 log n 层，每层 O(n)）
> 最坏呢？（有序输入 + 固定 pivot > 退化成 O(n²)）
> 怎么避免？（随机化 / 三数取中 / 三路快排）
> 为什么标准库不直接用快排？（最坏 O(n²)，所以用 Introsort 兜底）
> 那什么排序最坏也是 O(n log n)？（归并、堆排）
> 为什么不全用归并？（要 O(n) 额外空间，常数也大）和其他知识的连接
- < 来自 复杂度与数组、链表：复杂度分析是判断排序算法的基础；链表排序只能用归并（不能随机访问）
- < 来自 树与堆：堆排序、Top K 用堆
- > 影响 索引与 B+ 树：B+ 树叶子有序，所以
ORDER BY主键可以直接顺序读，不用排序 - > 影响 SQL 执行与优化：
ORDER BY超出内存时用外部排序（分块 + 多路归并） - > 影响 工程实践：
Arrays.sort的双轴快排、std::sort的 Introsort、Python 的 Timsort、数据库的索引有序性
自测 3 问
Q1：为什么快排在"已排序"的数组上反而最慢？
点开看答案
因为如果固定选第一个元素当 pivot，而数组已经有序：
- 第一次分区：pivot 是最小值，所有元素都在右边 > 分区结果是
[空] [n-1 个] - 第二次：又选最小值 > 又是
[空] [n-2 个] - ...
每次都只减少一个元素，递归深度 n，每层做 O(n) 的分区 > O(n²)。
这就是"最好的输入变成最坏的输入"的经典反例。解决：随机选 pivot，让"有序"不再导致固定选到极值。
Q2：二分找右边界时，mid 为什么要向上取整？
点开看答案
为了避免死循环。
考虑 left = 0, right = 1（相邻）。如果 mid = (left+right)/2 = 0（向下取整），而判断分支是 if (a[mid] <= target) left = mid：
- 如果条件成立，
left = 0> 没变 > 下一轮还是同样的left=0, right=1, mid=0> 无限循环。
改成向上取整 mid = (left+right+1)/2 = 1，则 left = 1，区间收缩，能正常退出。
记忆口诀：left = mid 的写法必须配向上取整；right = mid 的写法配向下取整。
Q3：为什么说 O(n log n) 是基于比较排序的下界？
点开看答案
用决策树论证：
n 个元素有 n! 种可能排列，排序算法必须能区分所有情况（输出正确的那个排列）。每次比较只有两个结果（是/否），所以决策树是一棵二叉树，叶子数 ≥ n!。
二叉树高度 ≥ log₂(n!)。由斯特林公式，log₂(n!) = Θ(n log n)。
所以任何基于比较的排序，最坏情况至少要 n log n 次比较。快排、归并、堆排都达到了这个下界，所以它们是最优的（在比较模型下）。
想突破只能用非比较排序（计数/基数/桶），它们不靠比较，而靠"数据的数值特性"直接定位。
类比失效处 / 易错点
- "理牌"类比（插入排序）会让人以为它很慢。小数组（<16）时插入排序比快排快，因为常数极小、缓存友好——所以标准库都用它处理小区间。
- "O(n log n) 都一样快"是错的。实测快排比堆排快 2~3 倍，差距全在缓存和常数。
- 快排不稳定，但"不稳定"不等于"结果错"。只影响相等元素的相对顺序。
- 二分不一定要求"数组有序"，只要求"能通过比较排除一半"。所以"旋转数组找最小值""找峰值"这类题也能二分，虽然数组整体无序。
(left+right)/2在 Java/C++ 里可能溢出。虽然数组长度通常达不到Integer.MAX_VALUE，但养成写left + (right-left)/2的习惯。
✅ 验收清单
- 能手写快排（含 partition），并说清最坏 O(n²) 的成因和三种优化
- 能手写归并排序，并解释"为什么归并是稳定的"
- 能对比快排/归并/堆排的复杂度、空间、稳定性、实际速度
- 能默写二分的两种写法（闭区间 / 左闭右开），并说清"为什么不能混"
- 能手写"找左边界"和"找右边界"，并解释右边界为什么要向上取整
- 能说出标准库为什么用混合排序（Introsort / Timsort），而不是单一算法
- 能用决策树论证"O(n log n) 是基于比较排序的下界"
- 合上书，用自己的话讲 3 分钟，中途不卡壳