2.5 Sorting Applications：排序选择、稳定性与问题归约

2.5 · Sorting Applications覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“2.5 · Sorting Applications”如何依据数据类型、稳定性、内存、输入分布与归约目标选择排序实现
能逐项核对排序应用、不同类型数据排序、排序算法选择、归约、稳定性与间接排序，并区分作者站内容与本页独立补充
能按“比较排序最坏比较下界为 ceil(log2(N!)) = Θ(N log N)”手算一个最小输入，逐步检查“输出必须全序且保持输入多重集；若合同要求稳定，相等键的原始次序也必须保持”
能注入“比较器违反传递性，或把 equals 与 compareTo 不一致的数据交给依赖全序的客户端”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“2·5 · Sorting Applications”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“2·5 · Sorting Applications”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“2·5 · Sorting Applications”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：2.5 · Sorting Applications

1. 排序应用：在本页通过“声明排序合同”连接解释、交互状态和练习验收。
2. 不同类型数据排序：在本页通过“选择比较器”连接解释、交互状态和练习验收。
3. 排序算法选择：在本页通过“选择排序实现”连接解释、交互状态和练习验收。
4. 归约：在本页通过“执行应用归约”连接解释、交互状态和练习验收。
5. 稳定性与间接排序：在本页通过“核对全序与稳定性”连接解释、交互状态和练习验收。

从“按城市分组后，时间顺序还在吗”开始

排序应用（sorting applications）关注的不是再写一个sort loop，而是先定义数据顺序，再按真实约束选择算法，最后把sorted order转化为业务答案。

先预测一批transactions原本按time到达，再按city排序后，同一city内是否仍按time。只有stable sort才能保证。若使用quicksort或heapsort，equal city records可能重排；结果按city正确，却丢掉隐含secondary key。稳定性在多阶段数据处理里不是装饰属性，而是可组合语义。

官方2.5依次讨论 Sorting various types of data、Which sorting algorithm should I use、Reductions、A brief survey of sorting applications。本节把这四部分连接成同一链：ordering contract、algorithm constraints、reduction proof、domain interpretation。

2.5.1 Sorting various types of data：顺序来自哪里

不同类型数据排序（sorting various types of data）通过Java callback把algorithm与key semantics分离。Natural order由 Comparable.compareTo 定义，适合一个canonical order；alternate ordering由 Comparator.compare 注入，适合同一record按date、amount、account或location等不同字段排序。

public final class Transaction implements Comparable<Transaction> {
    private final String who;
    private final Date when;
    private final double amount;
 
    @Override
    public int compareTo(Transaction that) {
        return this.when.compareTo(that.when);
    }
 
    public static final Comparator<Transaction> BY_AMOUNT =
        Comparator.comparingDouble(Transaction::amount);
}

比较器契约不能用“差值很小就相等”破坏transitivity。例如a近似b、b近似c却a明显大于c，会让sort没有一致目标。Integer comparison也不应直接 return a-b，因为overflow可反转order；使用 Integer.compare。

Pointer sorting在Java中移动object references，而不复制large record payload；因此exchange通常便宜。Key应immutable：sort结束后client若修改参与comparison的field，array可能立即不再sorted。若业务需要mutable records，应排序immutable projection、defensive copy或在mutation后重新建立order。

Primitive-specific sort避免boxing、virtual callback与reference indirection，但floating point必须定义NaN、positive/negative zero与total order。直接用 </> 拼comparator，NaN会让两个conditions都false，可能错误当作equal；应使用语言提供的Double.compare语义。

2.5.2 Stability and indirect sorting：保留identity与旧顺序

稳定性与间接排序（stability and indirect sorting）解决两个不同问题。Stability保护已有次序；indirect sort保护原数据布局。

若先按secondary key稳定排序，再按primary key稳定排序，最终order等价于lexicographic (primary, secondary)。官方本章算法中insertion sort与mergesort稳定；selection、Shellsort、quicksort和heapsort不稳定。不能只看平均速度表后忽略这个contract。

间接排序（indirect sorting）可实现：

Integer[] permutation = IntStream.range(0, records.length)
    .boxed()
    .toArray(Integer[]::new);
 
Arrays.sort(permutation, Comparator
    .comparingInt((Integer i) -> records[i].key())
    .thenComparingInt(i -> i));

Explicit original-index tie break可得到deterministic stable view，即使underlying sort不稳定；代价是额外N indices与indirection。一个dataset可同时持有by-date、by-location、by-amount多个permutations，避免复制或反复搬动records。

2.5.3 Sorting algorithm selection：约束决定起点

排序算法选择（sorting algorithm selection）没有单一答案。官方经验指出quicksort通常是最快general-purpose sort；但“通常”依赖不要求stability、随机化可接受、worst-case概率风险可接受。

选择时逐项问：

需要stable且有Theta(N) extra space：mergesort提供N log N worst-case。
需要constant array space和N log N worst-case：heapsort，但cache与常数较差且unstable。
General-purpose、平均速度优先：randomized quicksort；重复keys多时用three-way。
Input部分有序或N很小：insertion sort成本随inversions下降。
搬动极贵但比较便宜：selection sort的linear exchanges可能有价值。
Streaming top M或动态extreme：不做全排序，使用priority queue。

System sort的具体实现会随runtime版本变化，不能把某一历史Java选择当永久API contract；应查当前platform docs并以observable requirements验收。稳定性、exception behavior、parallelism与primitive/reference overload都比内部algorithm name更可靠。

2.5.4 Reductions：先排序，再线性扫描

归约（reductions）让sorting成为通用primitive。Proof要覆盖三步：transform保留什么语义、solver满足什么contract、output如何解释；只说“先sort”不够。

Dedup、distinct count、mode/frequency都利用equal keys在sorted array中连续。典型frequency scan：

Arrays.sort(words);
for (int i = 0; i < words.length; ) {
    int j = i + 1;
    while (j < words.length && words[j].equals(words[i])) j++;
    emit(words[i], j - i);
    i = j;
}

若comparison sort为N log N，后处理linear：

T_{\mathrm{sort+scan}}(N) =T_{\mathrm{sort}}(N)+\Theta(N) =\Theta(N\log N)

Frequency descending还需再排序distinct runs或放入priority queue。Memory与equivalence要进入contract：原数组是否可重排、case/locale是否区分、records能否只按projection聚合。

2.5.5 Rankings：Kendall tau归约为逆序计数

Kendall tau distance衡量两个permutations的pairwise disagreement。先构建第二ranking的inverse positions，再把第一ranking映射成position sequence；分歧pairs恰是该sequence inversions。

对rankings p与q：

K(p,q) =\left|\{(i,j)\mid i\lt j,\ q^{-1}(p_i)\gt q^{-1}(p_j)\}\right|

用mergesort merge阶段计inversions可在Theta(N log N)完成：right item先于left remaining items输出时，新增 mid-i+1 inversions。Brute force pair enumeration是Theta(N平方)。Precondition必须验证两inputs都是0到N-1的permutations；duplicates或missing labels会让inverse map无定义。

2.5.6 Selection与priority-queue reductions

Order statistics不一定需要full sort。Quickselect反复partition，只保留包含rank k的一侧；shuffle后expected linear：

while (hi > lo) {
    int j = partition(a, lo, hi);
    if      (j > k) hi = j - 1;
    else if (j < k) lo = j + 1;
    else            return a[j];
}
return a[lo];

其expected recurrence把每层linear partition与平均缩小subproblem相加：

\mathbb E[T_{\mathrm{select}}(N)]=\Theta(N)

但它会重排input，worst case仍quadratic，k是0-based rank且duplicates时返回任一等价key。若需要worst-case linear，要使用更复杂deterministic pivot selection；若需要很多不同k，full sort或selection data structure可能更合算。

Priority queue reductions处理streaming与multiway problems。TopM维护size M的min-PQ，每项insert，超限就delMin：

T_{\mathrm{TopM}}(N,M)=O(N\log M), \qquad S_{\mathrm{TopM}}=O(M)

Multiway merge为M个sorted streams各放一个head到min-PQ，删除最小head后从同一stream补next，时间 O(N log M)、额外queue O(M)。这些方案不需要把全部N项同时放内存，也不需要全局重新sort。

2.5.7 Brief survey：排序进入其他算法

商业计算按name、account、time、location、postal code或file date组织records；sorted order再支持binary search与group scans。Operations research中SPT按processing time升序最小化single-machine平均completion time；LPT按descending jobs并把next job交给最早available processor，为NP-hard load balancing提供近似。

Event-driven simulation用priority queue取next chronological event。Graph algorithms中Kruskal先按edge weight排序，Prim与Dijkstra用indexed PQ。Huffman compression反复合并两个minimum frequencies。String processing先排序domains、suffixes或reversed words，把共同prefix/suffix结构变成相邻关系。

这些应用的共同模式是“order creates locality”：原本散落的equal、nearby、next、minimum或same-prefix items，经排序或PQ后变得可连续处理。但归约是否有益取决于query count、streaming、memory与key computation；一次linear scan能解决的问题不应强行sort。

统一验收：从ordering contract到domain answer

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“2.5 · Sorting Applications”的两个最小情境间切换，再逐项选择正式概念。预测“比较排序最坏比较下界为 ceil(log2(N!)) = Θ(N log N)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

2.5 · Sorting Applications：对象、操作与不变量

依据数据类型、稳定性、内存、输入分布与归约目标选择排序实现

选择最小情境

切换正式概念

稳定多键: 先按姓名排序，再稳定地按部门排序
当前观察: sorting applications：部门相同记录仍保持姓名顺序，形成多键结果

比较排序最坏比较下界为 ceil(log2(N!)) = Θ(N log N)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

排序应用：在实验 1 中指出对应状态，并写出一个通过条件。
不同类型数据排序：在实验 2 中指出对应状态，并写出一个通过条件。
排序算法选择：在实验 3 中指出对应状态，并写出一个通过条件。
归约：在实验 1 中指出对应状态，并写出一个通过条件。
稳定性与间接排序：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“比较排序最坏比较下界为 ceil(log2(N!)) = Θ(N log N)”不是孤立结论？

问题 3：故障恢复。 怎样证明“比较器违反传递性，或把 equals 与 compareTo 不一致的数据交给依赖全序的客户端”已经修复？

保存数据类型、比较器、原始序号、排序结果、稳定性、峰值空间与归约后的答案作为正常基线；注入该故障并标记第一个违反“输出必须全序且保持输入多重集；若合同要求稳定，相等键的原始次序也必须保持”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Sorting applications从ordering contract开始，不从algorithm name开始。
Comparable给natural order，Comparator给alternate orders；keys与comparison relation必须稳定一致。
Stable sort保留equal-key旧顺序，indirect sort返回permutation而不移动records。
Algorithm selection要同时看stability、space、worst case、duplicates、presortedness与movement。
Sort-and-scan把dedup、frequency和mode等问题归约到N log N。
Kendall tau通过inverse ranking映射为inversion count；quickselect只追踪rank k一侧。
TopM与multiway merge用size-M PQ把时间降到N log M并保持streaming。