1 / 4概念
Sorting & Searching
排序把无序输入变成全序,查找再利用这个全序把候选集砍半。判断标准不是“哪个排序最快”,而是数据规模、比较代价、稳定性、内存和输入分布。
1 概念
1.1 一句话定义
排序把 n 个元素按给定比较关系排成非降或非升序列;查找在给定结构中定位满足条件的元素。两者共享同一个前提:元素之间必须存在可比较的全序。
1.2 它解决什么问题
- 输出有序:报表、分页、合并、去重、top-k 都依赖顺序。
- 查找加速:有序数组二分是 O(log n),无序线性扫描是 O(n)。
- 算法前置:扫描线、区间合并、双指针、并查集预处理都要求先排序。
没有排序,这些场景只能退化为嵌套扫描;没有查找结构,每次查询都要重新遍历。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 渐进分析与复杂度记号 | Complexity Analysis |
| 堆、平衡树、哈希表 | Trees & Heaps、Linear Structures |
| 图的最短路与最小生成树 | Graph Algorithms |
| 数据库排序、索引与执行计划 | Indexing & Optimization |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 稳定性 | 相等键保持原始相对顺序 | 不是“排序结果是否确定” |
| 原地 | 额外空间 O(1) 或 O(log n) | 不是“完全不分配内存” |
| 比较模型 | 只能通过 <、=、> 获取信息 | 计数/基数排序不受此限 |
| 下界 | 比较排序需要 Ω(n log n) 次比较 | 是模型下界,不是所有排序的下界 |
| 在线 | 数据逐个到达时仍能维护有序 | 插入排序在线,快排不在线 |
2 机制
2.1 心智模型
比较排序是一棵决策树:每次比较只给出一个 bit,n! 种排列需要至少 log₂(n!) ≈ n log n 个叶子,所以比较排序不可能更快。二分查找则是每次把候选区间砍半,前提是区间已经有序。
2.2 机制拆解
- 快排:选 pivot → 分区 → 递归。平均 O(n log n),最坏 O(n²),原地但不稳定。
- 归并:对半切 → 递归 → 线性合并。稳定,最坏 O(n log n),数组实现需要 O(n) 额外空间。
- 二分:维护
[lo, hi)候选区间,每次比较 mid 并丢弃一半;循环不变量是“答案若存在,必在区间内”。
2.3 完整枚举
比较排序:
| 算法 | 平均 | 最坏 | 额外空间 | 稳定 | 原地 | 备注 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 是 | 是 | 小数组、近有序 |
| 选择排序 | O(n²) | O(n²) | O(1) | 否 | 是 | 比较次数固定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 是 | 是 | 教学用,工程少用 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | 否 | 链表、外部排序 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 | 是 | 常数小,怕对抗输入 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 是 | 常数大,内存紧张 |
| 希尔排序 | O(n log² n) | O(n²) | O(1) | 否 | 是 | 增量序列决定性能 |
| Timsort | O(n log n) | O(n log n) | O(n) | 是 | 否 | 利用已有 run,近有序 O(n) |
非比较排序:
| 算法 | 复杂度 | 限制 | 适用 |
|---|---|---|---|
| 计数排序 | O(n + k) | k 为值域,需整数 | 年龄、分数等小范围整数 |
| 基数排序 | O(d(n + k)) | 定长键、按位稳定 | 定长字符串、整数 ID |
| 桶排序 | 平均 O(n + k) | 数据需均匀分布 | 浮点、分位数 |
查找:
| 算法 | 复杂度 | 前提 | 适用 |
|---|---|---|---|
| 线性查找 | O(n) | 无 | 小数组、无序 |
| 二分查找 | O(log n) | 已排序、可随机访问 | 静态有序数组 |
| 插值查找 | 平均 O(log log n) | 均匀分布 | 数值均匀的大数组 |
| 指数查找 | O(log n) | 已排序、无界或未知长度 | 无界流、跳表式探测 |
| 哈希查找 | 平均 O(1) | 有哈希表、可接受最坏 O(n) | 高频点查 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 比较排序下界 | Ω(n log n) | 决策树叶子数决定 |
| 二分查找 | O(log n) | 每次候选集减半 |
| 快排最坏 | O(n²) | 已排序 + 首元素 pivot 是经典触发 |
| 归并额外空间 | O(n) | 数组实现;链表可做到 O(1) |
| Timsort 最好 | O(n) | 已排序输入只做一次扫描 |
| 计数排序 | O(n + k) | k 是值域,值域大时退化 |
3 实践
3.1 最小示例
// 二分查找:返回 target 的下标,找不到返回 -1。
// 循环不变量:答案若存在,一定在 [lo, hi) 内。
export function binarySearch(values: readonly number[], target: number): number {
let lo = 0;
let hi = values.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo < values.length && values[lo] === target ? lo : -1;
}
// 默认 sort 会把元素转成字符串;数字必须显式给比较器。
const sorted = [...values].sort((a, b) => a - b);
3.2 常用操作与参数
| 操作 | 命令 / API | 说明 |
|---|---|---|
| 数组排序 | xs.sort(cmp) / xs.toSorted(cmp) | toSorted 返回副本,不改原数组 |
| 稳定排序 | 现代引擎的 Array.prototype.sort | ES2019 起要求稳定 |
| 二分插入点 | 手写 lower_bound / _.sortedIndex | 返回第一个不小于目标的位置 |
| 数据库排序 | ORDER BY + 合适索引 | 索引有序时可避免额外排序 |
| top-k | 堆 / heapq.nlargest | O(n log k),不必全排序 |
3.3 标准流程
- 明确是否需要稳定排序、是否允许 O(n) 额外内存。
- 估计 n、比较代价、值域和输入分布。
- 选算法;对抗输入用 introsort/Timsort,不要裸快排。
- 写比较器,保证全序、传递、反对称。
- 测空数组、单元素、全相等、已排序、逆序、NaN/undefined。
3.4 与相邻技术的组合
- 排序 + 双指针:区间合并、两数之和、去重。
- 堆:top-k、优先队列、合并 K 个有序链表。
- 数据库:
ORDER BY走索引可以避免排序;否则会落盘。 - 搜索:倒排索引的 posting list 通常按 doc id 有序,便于交集。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| n | 小 / 大 | 小数组用插入排序 |
| 比较代价 | 便宜 / 昂贵 | 昂贵时减少比较次数 |
| 内存 | 紧张 / 充足 | 原地快排 vs 归并 |
| 稳定性 | 需要 / 不需要 | 归并/Timsort vs 快排/堆 |
| 值域 | 有界整数 / 任意 | 计数/基数 vs 比较排序 |
| 输入分布 | 随机 / 近有序 / 对抗 | 快排退化风险 |
3.6 决策规则
- n ≤ 16:插入排序,常数比递归排序小。
- 需要稳定或输入近有序:归并/Timsort。
- 内存紧张且无对抗输入:快排/introsort。
- 值域小且有界:计数/基数排序。
- 只需要 top-k:堆,不要全排序。
- 查找:静态有序用二分;频繁动态查询用哈希/平衡树。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 快排 | 原地、常数小 | 最坏 O(n²)、不稳定 | 一般数组 |
| 归并 | 稳定、最坏 O(n log n) | O(n) 额外空间 | 链表、外部排序 |
| 堆排序 | 原地、最坏 O(n log n) | 常数大、不稳定 | 内存紧张 |
| Timsort | 近有序 O(n) | 实现复杂 | 真实业务数据 |
| 计数/基数 | O(n + k) | 受值域/位数限制 | 整数、定长键 |
3.8 何时不该用
- 只要最大/最小/top-k:用堆或选择,不要全排序。
- 数据已经有序:插入/归并的 O(n) 分支,不要快排。
- 查找频繁但数据动态:哈希/平衡树,不要每次排序后二分。
- 比较器有副作用或不一致:先修 comparator,换算法没用。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 排序结果随机错乱 | comparator 不满足传递性,或返回 boolean | 返回负数/0/正数 |
| 数字按字典序排 | 默认 sort 把元素转字符串 | 提供 (a, b) => a - b |
| 快排栈溢出 | 已排序 + 首元素 pivot | 随机 pivot、三数取中或 introsort |
| 二分死循环 | lo = mid 没有收缩区间 | 用 [lo, hi) 且 hi = mid |
| 重复元素顺序变了 | 用了不稳定排序 | 归并/Timsort 或加 tie-breaker |
| NaN/undefined 位置错 | 比较返回 NaN | 先清洗数据,或定义明确顺序 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 循环内排序 | O(n² log n) | 一次排序或堆 |
| 用 sort 做 top-k | 全量 O(n log n) | 堆 O(n log k) |
| 机器排序用 localeCompare | 结果随 locale 变化 | 明确 Unicode/字节序 |
| 原地 sort 共享数组 | 调用方数据被改 | toSorted 或副本 |
4.3 可观测信号
比较次数、运行时间、额外内存、递归深度、输入是否近有序。基准测试要覆盖已排序、逆序、全相等、随机和对抗输入。
4.4 安全 / 性能 / 一致性边界
- 比较排序的下界是 Ω(n log n),不要承诺更低的通用比较排序。
- 二分查找的前提是已排序;无序数据上的二分是未定义行为。
- 稳定性需要额外空间或 tie-breaker,不是免费的。
- 外部排序受 I/O 限制,算法复杂度不是唯一瓶颈。