主题
界面
基础算法：排序与二分查找
1. 本节定位
《树、堆与哈希表》讲了"按 key 精确查找"；本节讲**"有序"带来的能力**：
text
排序本身是 O(n log n) 的"重活"，
但它开启了：二分查找 O(log n) → 范围查询 → 去重 → Top K → 归并本节的核心不是"背排序算法" ✗ ——而是：
知道"什么时候该排序"、以及"为什么业务代码永远用
Arrays.sort" ✓✓
2. 学习目标
- 能说出六种排序的复杂度与实测差距 ★★★；
- 知道快速排序最坏情况会怎样（不只是变慢，而是栈溢出）★★★；
- 知道 JDK 的
Arrays.sort内部用了什么策略 ★★； - 知道"稳定排序"的意义与它的实际用途 ★★★；
- 知道二分查找的前提与威力 ★★★。
3. 前置知识检查
- 知道复杂度的含义吗？（《时间复杂度和空间复杂度》）✓
- 会用
Arrays.sort与Comparator吗？（《注解基础》）✓
4. 为什么需要这个知识
先看一个"自己写排序"的真实代价 ✗：
text
某项目为了"处理特殊比较规则"，手写了一个冒泡排序
数据量：每批 5 万条
结果：单批耗时 200 ms，一天跑 5000 批 → 16 分钟纯排序 ✗
换成 Arrays.sort + Comparator 后：每批 5 ms → 25 秒 ✓✓★★ 更隐蔽的是"写错" ✗：
手写排序最容易出的 bug 不是"慢"，而是"边界条件写错" ✗✗
比如快排的分区边界、归并的临时数组长度、下标的
<=与<✓这些错误在小数据上"看起来是对的"，在特定数据分布上才暴露 ✓
5. 核心概念
5.1 六种排序的实测对比 ★★★
实测数据（单位 ms）：
text
算法 1万 10万 100万
冒泡排序 O(n²) 78 （跳过） （跳过）
插入排序 O(n²) 30 （跳过） （跳过）
快速排序 O(n log n) 2 15 170
归并排序 O(n log n) 3 34 259
堆排序 O(n log n) 2 16 180
Arrays.sort（双轴快排） 1 8 100 ← 最快 ✓✓★ 三点结论 ✓：
| # | 结论 |
|---|---|
| ① | O(n²) 在 1 万就要几十毫秒 ✗ ——10 万已经不适合做交互式功能 ✓ |
| ② | 三种 O(n log n) 排序在同一量级 ✓ ——差别在常数（快排 < 堆排 < 归并）✓ |
| ③ | Arrays.sort 比手写快排还快一倍 ★★ ——因为它有更多优化 ✓ |
★ Arrays.sort 内部的优化（这是"别手写"的真正理由） ✓✓：
| 优化 | 作用 |
|---|---|
| 双轴快排（Dual-Pivot Quicksort） ★★ | 两个基准，分区更均衡 ✓ |
| 小数组切插入排序 ★ | 长度 < 47 时用插入排序（小数组上它更快）✓ |
| 三数取中选基准 ★ | 避免有序数据导致的退化 ✓ |
| 深度超限切堆排序 ★★ | 递归太深时改用堆排，保证 O(n log n) 上界 ✓ |
★ 最后一条正好治了本节的实测问题 ✓✓（见 5.2）✓
5.2 快速排序的退化：不只是变慢，而是栈溢出 ★★★
实测结果（这是本节最有价值的数据）：
text
朴素快排 + 随机数据： 2 ms ✓
朴素快排 + 已有序： StackOverflowError ✗✗（递归深度 = n）
Arrays.sort + 已有序： 1 ms ← 依然很快 ✓★★ 注意：它"崩了"，而不是"变慢了" ✓✓ ——这比复杂度退化严重得多 ✓
为什么 ✓：
text
朴素快排固定取"第一个元素"为基准
↓
遇到已排序数组时，每次分区都极度不均（1 : n-1）
↓
递归深度 = n（而不是 log n）
↓
3 万元素 → 递归 3 万层 → 每层占一个栈帧 → 栈溢出 ✗✗★ 这个真实案例的价值 ✓✓：
| 教训 | 说明 |
|---|---|
| "最坏情况"是真实存在的 ★★ | 而且现实数据常常"接近有序"（如按时间录入的数据）✓ |
| 递归算法的"深度"和"复杂度"是两件事 ★★★ | 复杂度 O(n log n) 说的是比较次数，深度可能是 O(n) ✓✓ |
| JDK 的应对是"深度超限就换堆排序" ★★ | 它把最坏情况的上界钉死在 O(n log n) ✓ |
★ 给工程人的结论 ✓：
业务代码永远用
Arrays.sort/Collections.sort/List.sort✓✓手写排序只在两处有意义：面试、以及"排序规则本身就是业务核心"的场景（如自定义的流式 Top K）✓
5.3 稳定排序：一个容易被忽略的性质 ★★★
"稳定"的含义：相等的元素，排序后保持原来的相对顺序 ✓
★ 它是多级排序的基础 ✓✓：
java
// 需求：先按价格升序，价格相同的按销量降序
// 错误做法：直接写一个"两个 key 都判断"的 Comparator（容易写错，见下）
// 正确做法（利用稳定性）：从"次要键"到"主要键"倒着排
list.sort(Comparator.comparingInt(Product::sales).reversed()); // 先按次要键
list.sort(Comparator.comparingDouble(Product::price)); // 再按主要键（稳定，不打乱上一步）★ 为什么"倒着排"能成立 ✓：
第二次排序是稳定的 → 它不会打乱"价格相同的那批元素内部已有的销量顺序" ✓✓
而那批元素内部的顺序，正是第一次排序的结果 ✓
★ 实测数据（两种类型用不同算法） ✓：
text
Arrays.sort(int[]) 50 万个： 快（双轴快排，不稳定）
Arrays.sort(Integer[]) 50 万个： 稍慢（TimSort，稳定）★ 为什么基本类型用"不稳定"的快排 ✓✓：
| 类型 | 算法 | 原因 |
|---|---|---|
int[] / long[] ★ | 双轴快排（不稳定） | 基本类型没有"身份"，相等就是相等 ——稳定性无意义 ✓ |
Integer[] / 对象数组 / List ★★ | TimSort（稳定） | 对象"相等"但可能不是同一个，顺序可能有业务含义 ✓ |
★ 一个性能上的引申 ✓：
TimSort 需要额外的临时空间（O(n)）✗ ——而双轴快排是原地排序 ✓
所以"用
Integer[]排序比int[]慢"不只是装箱的代价 ✓✓
5.4 二分查找：O(log n) 的威力 ★★★
实测/理论对比：
| 数据规模 | 线性查找 | 二分查找 | 二分比较次数 |
|---|---|---|---|
| 1 千 | 微秒级 | 微秒级 | 10 次 |
| 100 万 | 毫秒级 | 微秒级 | 20 次 |
| 10 亿 ★★ | 秒级 ✗ | 微秒级 ✓ | 30 次 ✓✓ |
★ "10 亿只要 30 次比较"是本节最该记住的数字 ✓✓
三个必须记住的前提 ✗：
| 前提 | 说明 |
|---|---|
| 数据必须有序 ★★★ | 否则要先排序（O(n log n)） ✓ |
| 必须支持随机访问 ★★ | ArrayList 可以，LinkedList 不行 ✗（《数据结构：数组、链表、栈与队列》：get(i) 是 O(n)） |
| 数据要"能比较" | Comparable 或 Comparator ✓ |
★ 第二条很容易被忽略 ✓：
java
// ✗ 对 LinkedList 用二分：每次 get(mid) 都是 O(n)，总复杂度退化成 O(n log n)
Collections.binarySearch(linkedList, key);
// ✓ 对 ArrayList：get(mid) 是 O(1)，总复杂度 O(log n)
Collections.binarySearch(arrayList, key);★ 边界写法的两个口诀（也可以直接用 JDK 的）✓：
java
// JDK 提供（推荐直接用）
Arrays.binarySearch(sortedArray, key); // 找到返回下标，否则返回 -(插入点+1) ✓
Collections.binarySearch(sortedList, key);
// 自己写时的两个变体（见 S2-008 模板）
// lowerBound：第一个 >= target 的位置
// upperBound：第一个 > target 的位置★ 注意 binarySearch 的返回值约定 ✓：
java
int idx = Arrays.binarySearch(arr, key);
if (idx >= 0) { /* 找到了 */ }
else { /* 没找到，插入点是 -(idx + 1) */ } // ★ 别写成 -idx 或 idx*-1★ 这条约定很有用：它同时告诉了你"没找到"和"该插在哪" ✓✓
5.5 排序在工程里的三种用法 ★★
| 用法 | 说明 |
|---|---|
| 为二分/范围查询做预处理 ★★ | 排一次 O(n log n)，之后每次查询 O(log n) ✓ |
| 让"去重"变简单 ★ | 排序后相邻比较即可（O(n)）✓ |
| 让"合并/连接"变简单 ★★ | 归并思想：两个有序数组合并是 O(n) ✓ |
★ 一个典型场景 ✓：
text
需求：从 100 万个订单里，找出"每个用户最近一笔"
做法 A：按用户分组，每组内找最大时间 → 需要哈希 + 遍历
做法 B：先按 (userId, time) 排序，再顺序扫一遍取每组第一条 ← 排序后一次扫描 ✓✓★ 但要注意：排序 O(n log n) 不总是最优 ✗ ——如果只需要"最大值"，一次遍历（O(n)）就够了 ✓
判断口诀："要不要全局有序？要 → 排序；只要极值 → 遍历或堆" ✓✓
6. 递进示例
6.1 最小示例
java
int[] a = {5, 2, 9, 1};
Arrays.sort(a); // ✓ 基本类型升序
List<Product> list = ...;
list.sort(Comparator.comparingDouble(Product::price)); // ✓ 对象排序6.2 业务示例：多级排序（靠稳定性）
见 5.3 ✓
6.3 反例：手写冒泡处理 5 万条
见第 4 节 ✓
7. 完整可运行代码与实测
代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/SortingLesson.java
运行：
powershell
cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.SortingLesson实测输出（关键部分）：
text
===== 1. 六种排序的实测耗时（单位 ms）=====
算法 1万 10万 100万
冒泡排序 O(n²) 78 太慢跳过 太慢跳过
插入排序 O(n²) 30 太慢跳过 太慢跳过
快速排序 O(n log n) 2 15 170
归并排序 O(n log n) 3 34 259
堆排序 O(n log n) 2 16 180
Arrays.sort（双轴快排） 1 8 100
===== 2. 快速排序的退化 =====
朴素快排 + 随机数据：2 ms ✓
朴素快排 + 已有序： StackOverflowError ✗✗（递归深度 = n）
Arrays.sort + 已有序：1 ms ← 依然很快 ✓★ 三条可落地的结论 ✓：
| # | 结论 | 依据 |
|---|---|---|
| ① | 一律用 Arrays.sort / List.sort | 它比手写快排快一倍，且无退化风险 ✓ |
| ② | "已排序数据"是朴素快排的天敌 | 直接栈溢出 ✗✗ |
| ③ | 多级排序用"从次要键到主要键倒着排" | 依赖稳定排序 ✓ |
8. Debug 观察点
- 把已有序数组的长度调到 10 万：观察崩得更彻底（甚至线程直接死亡）✗；
- 把
Arrays.sort换成list.sort对Integer列表：观察耗时差异（TimSort vs 双轴快排）★； - 用
Collections.binarySearch查一个不存在的 key：观察返回值是负数 ✓； - 把二分查找用到
LinkedList上：观察耗时暴增 ★★； - 比较"先排序再二分"与"直接遍历"的耗时拐点：找出排序划算的临界规模 ✓。
9. 常见错误
| # | 错误 | 说明 |
|---|---|---|
| 1 | 手写排序进生产代码 ✗✗ | 慢且易错（5.1、5.2）✗ |
| 2 | 忽略"已排序数据"对朴素快排的杀伤 ✗✗ | 栈溢出，不是变慢 ✓ |
| 3 | 在对 LinkedList 用二分查找 ✗✗ | get(mid) 是 O(n)，总复杂度退化 ✓ |
| 4 | 多级排序写一个"巨大的 Comparator" ⚠️ | 容易写反 ——用"倒着排 + 稳定性"更清晰 ✓ |
| 5 | binarySearch 没找到时把返回值直接当下标用 ✗✗ | 要 -(idx+1) 才是插入点 ✓ |
| 6 | 以为 int[] 与 Integer[] 的排序一样 ✗ | 不同算法（快排 vs TimSort）✓ |
| 7 | 对"只要极值"的场景先排序 ✗ | 一次遍历 O(n) 就够 ✓ |
10. 动手实验
目标：亲手复现"快排崩溃"，并形成"用 JDK 排序"的习惯。
步骤：
- 跑
SortingLesson，确认Arrays.sort在各档都最快 ✓； - 把快排退化的数据量从 3 万改成 5 万，观察崩溃 ✗；
- 给朴素快排加"三数取中"，再跑一次 → 观察它不再崩溃 ★★；
- 对同一个列表做"多级排序"：分别用"大 Comparator"与"倒着排"，验证结果一致 ✓；
- 测"先排序再二分查 1000 次"与"遍历 1000 次"的耗时拐点（n 从 100 涨到 10 万）★。
验收方式：能说出"朴素快排在什么数据上会崩，怎么修"。
扩展任务：读一段 java.util.Arrays.sort 的源码（或用 javap 看调用链）：
- 找到"小数组切插入排序"的阈值（提示：
INSERTION_SORT_THRESHOLD，值是 47）✓； - 找到"深度超限切堆排序"的逻辑（提示：
depthLimit与heapSort）✓； - 说明：这两条优化分别解决了什么问题 ★★
11. 练习题
- 判断：快速排序的最坏情况只是变慢。（对 / 错）
- 填空：
Arrays.sort(int[])用的是 ______（不稳定）；Arrays.sort(Integer[])用的是 ______（稳定）。 - 简答：为什么"多级排序"要"从次要键到主要键倒着排"？
- （代码阅读）
java
LinkedList<Integer> list = new LinkedList<>(sortedData);
int idx = Collections.binarySearch(list, 500);问题在哪？ 5. （编程）不调用 Collections.sort，用"归并"思想合并两个已排序数组（O(n)），并说明它比"合并后再排序"好在哪。
参考答案（要点）
- 错。朴素快排跑已排序数据会栈溢出 ✗✗（本节的实测）✓★
- 双轴快排；TimSort ✓
- 因为第二次排序是稳定的，不会打乱"主要键相同的那批元素内部已有的顺序" ✓ —— 而那批内部的顺序正是第一次排序（次要键）的结果 ✓★
LinkedList不支持随机访问 ✗ ——get(mid)是 O(n)，二分总复杂度退化成 O(n log n) ✓- 要点：双指针从两数组头开始比较，小的先放入结果 ✓ 好在：O(n) vs 排序的 O(n log n)，且不需要额外排序 ✓
12. 掌握标准
- [ ] 能说出六种排序的复杂度与实测量级 ★★★；
- [ ] 知道朴素快排跑有序数据会栈溢出 ★★★；
- [ ] 知道
Arrays.sort的四条内部优化 ★★； - [ ] 知道稳定排序的含义，并会用"倒着排"做多级排序 ★★★；
- [ ] 知道二分查找的三个前提，尤其"必须支持随机访问" ★★★；
- [ ] 会正确处理
binarySearch的负数返回值 ★★； - [ ] 知道"只要极值就不要排序" ✓。
13. 扩展资源
14. 下一步学习
《递归、分治与动态规划》：从"套循环"升级到"分解问题"。
进度只保存在本机浏览器，可随时清除