第7章 Sorting Strings：字符串排序

以区分前缀刻画字符读取下界，比较 MSD/LSD 基数排序与多关键字快速排序，并分析变长字符串在两级存储中的拆分模型。

学习目标

能解释“7 Sorting Strings”如何用区分前缀、基数分桶与多关键字快速排序减少字符检查
能逐项核对A Lower Bound、RADIXSORT、Multi-key QUICKSORT、Some Observations on the Two-Level Memory Model∞，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“character work = Theta(D + n log n)”手算一个最小样例，并找到输出或成本的首个分叉
能注入“终止符、字符编码或稳定性约定不一致，前缀串与长串次序被颠倒”，保存基线、故障、恢复和同输入重放证据

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

“7 Sorting Strings”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“7 Sorting Strings”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“用区分前缀、基数分桶与多关键字快速排序减少字符检查”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：7 Sorting Strings

7.1 A Lower Bound：在本页正文中以“用区分前缀、基数分桶与多关键字快速排序减少字符检查”的对象、状态、复杂度或工程边界核对。
7.2 RADIXSORT：在本页正文中以“用区分前缀、基数分桶与多关键字快速排序减少字符检查”的对象、状态、复杂度或工程边界核对。
7.3 Multi-key QUICKSORT：在本页正文中以“用区分前缀、基数分桶与多关键字快速排序减少字符检查”的对象、状态、复杂度或工程边界核对。
7.4 Some Observations on the Two-Level Memory Model∞：在本页正文中以“用区分前缀、基数分桶与多关键字快速排序减少字符检查”的对象、状态、复杂度或工程边界核对。

从“交换指针很便宜”为何仍然很慢开始

sorting strings与第5章原子项排序不同。字符串通常由指针数组引用，比较两个指针指向的正文时，要从头逐字符找首个 mismatch。

普通 Mergesort 或 Quicksort 做 Theta(n log n) 次字符串比较；若平均字符串长 L=N/n，每次最坏读 O(L) 字符，粗略上界达到 O(N log n)。更糟的是，同一公共前缀会在不同比较中反复读取，字符串正文与指针数组还会争夺缓存。

先预测 all、ally、also、alter 四个词是否必须全部读完才能排序。all 与 ally 在前三个字符后由“结束”与 y 区分；also 读到第三个字符 s 已与 ll 分开；alter 也只需读到 t 附近。字符尾部若不再影响与其他字符串的相对顺序，就没有信息论理由继续读取。

区分前缀给出更细的下界

对字符串 s，令 d_s 为能把它与集合中其余字符串区分开的最短前缀长度。总量为：

d = \sum_{s\in S}d_s

任何正确算法至少要检查这些字符，否则无法排除两个字符串仍共享未读前缀；同时，比较模型仍需决定 n 个对象的顺序。因此 string sorting lower bound（字符串排序下界）为：

\Omega(d+n\log n)

这可以小于读取全部 N 个字符。当字符串有很长、互不影响排序的尾部时，d 远小于 N。相反，n 个字符串共享很长前缀、只在末尾区分时，d 与 N 同阶；普通比较排序仍可能重复公共前缀达 log n 次，比下界多一个对数。

下界中的字符“比较”还取决于编码与 collation 规则。按 UTF-8 字节排序、按 Unicode code point 排序、按语言区域排序会给出不同顺序；算法必须先固定字符命名和结束符次序。

MSD-first 基数排序：只深入仍有冲突的桶

RADIXSORT先把字母表命名为0到 sigma-1的有序整数。

MSD-first 从最显著字符，也就是字符串开头处理。按偏移 i 的 digit 分到 sigma 个桶；单元素桶已确定，只有多元素桶递归到 i+1。连接各桶即得到字典序。

MSDRadix(strings, offset):
  if strings has at most one item: return
  buckets = distribute by char_at(string, offset)
  for bucket in character order:
    if bucket is not END:
      MSDRadix(bucket, offset + 1)
  concatenate buckets

递归分桶隐式构造 sigma 叉 trie：所有经过同一节点的字符串共享该前缀，分支节点对应首个不同字符。若每个节点直接分配 sigma 槽数组，时间和空间可达 O(d sigma)；改用按实际边数分配的哈希表，再排序每个节点的边，可得到平均 O(d log sigma) 时间、O(d) 空间。

压缩连续单孩子路径可把 trie 结构空间进一步接近 O(n)，路径标签保存被压缩前缀长度；第9章会把它作为搜索结构展开。

LSD-first 基数排序：稳定性把低位次序带到高位

LSD-first 从最低位向最高位逐列排序。它适合等长字符串；变长字符串可在左侧逻辑补小于真实 digit 的哨兵，使短串与长串对齐，但实现必须与目标字典序一致。

每一列必须使用。当前高位相等时，前一阶段按低位建立的相对顺序才能保留。

长度都为 L、字母表大小 sigma 时，CountingSort 每轮 O(n+sigma)，总时间：

T_{\mathrm{LSD}} = O(L(n+\sigma)) = O(N+L\sigma)

若字符串各有 b 个二进制位，每轮处理 r 位 digit，需要 b/r 轮，每轮桶数 2 的 r 次方：

T(r) = \Theta\left( \frac{b}{r}(n+2^r) \right)

r 远小于 log n 时轮数过多；r 远大于 log n 时桶数组爆炸。取 r 为 Theta(log n) 平衡二者，时间约 O(bn/log n)，但 CountingSort 需要 Theta(n) 辅助空间。

MSD 可在区分后跳过尾部，LSD 无论内容都扫描所有 digit；但 LSD 是规则的全量 pass，没有 trie 动态分配，连续内存上可能有更低常数。应根据 d/N、固定长度、字母表和内存预算选择。

多关键字快速排序：比较字符而不是整串

multi-key QUICKSORT把第5章三路 Quicksort 提升到字符级。

对字符串集合 R 和偏移 i，随机选 pivot string p，以 p[i] 为 pivot 字符，划分：

R_less 的第 i 字符较小，递归仍用 i；
R_equal 的第 i 字符相同，递归推进 i+1；
R_greater 的第 i 字符较大，递归仍用 i。

MultikeyQS(R, i):
  if size(R) <= 1: return R
  p = random string from R
  pivot = char_at(p, i)
  (less, equal, greater) =
      three_way_partition(R, i, pivot)
  A = MultikeyQS(less, i)
  B = pivot == END ? equal : MultikeyQS(equal, i + 1)
  C = MultikeyQS(greater, i)
  return concatenate(A, B, C)

正确性不变式是：进入 MultikeyQS(R,i) 时，R 中字符串在前 i 个字符之前已共享或已按字典序分组。小/大桶只知道当前字符相对 pivot 的方向，桶内仍需比较 i；相等桶已共享当前字符，才能推进。

对每个字符串，偏移最多推进到其区分前缀，集合规模在良好 pivot 下最多缩小 O(log n) 次。平均字符比较：

O(d+n\log n)

与比较模型下界匹配。用确定性线性选择中位字符可转为最坏界；实践中随机 pivot 或小样本中位数更简单。算法不建立显式 trie，只重排指针并携带偏移，空间通常更紧凑。

假设让每对字符串最终存在 mismatch。真实代码通常不修改字符串，而是让 char_at 在长度位置返回 END；重复字符串则落入 END 相等桶，必须直接结束而非无限推进。

MSD 与多关键字快排的树形对应

MSD RadixSort 构造 sigma 叉 trie；多关键字快排对应 ternary search tree：每个节点有低、等、高三条路径。低/高子树保持字符偏移，等子树推进一个字符。

平衡 ternary tree 搜索长度 p 的模式，需要至多 p+log n 次字符比较：p 次沿等边消费模式，log n 次在同一偏移上走低/高平衡树。这个结构解释了多关键字快排为何同时具有“按前缀推进”和“按集合规模缩小”两部分成本。

两级存储模型中字符串能否拆分很关键

two-level memory model（两级存储模型）分析字符串时，变长记录是否可以在外存拆成字符不是小实现细节。本页区分：

Model A：字符串在外存基本不可分，只允许长串按 B 大块移动；
Model B：读入内部存储后可以拆字符，外存仍按完整记录/块管理；
Model C：内外存都可拆分，允许对片段做随机哈希等操作。

Model A 倾向用多路 Mergesort 和内部 lazy trie 引导比较。令 n_s、N_s 为短于 B 的字符串数与总长，n_l、N_l 为长串对应量，其最优 I/O 包含排序短串字符、排序长串首块与读取全部数据三部分：

\Theta\left( \frac{N_s}{B}\log_{M/B}\frac{N_s}{B} +n_l\log_{M/B}n_l +\frac{N_s+N_l}{B} \right)

Model B 允许在内存拆字符，长串排序的对数底数可从 M/B 提升到 M，证明细粒度比较有实质价值。Model C 更强，可随机哈希片段缩短字符串，但 hash 不保持字典序，必须在排序流程中谨慎选择片段并最终验证次序。

工程实现要记录字符串布局：正文连续还是分散分配、指针宽度、长度前缀、跨页字符串比例、重复前缀长度和缓存 miss。只报告比较次数会漏掉真正 I/O。

正确性与性能一起验证

正确性预言机可以用语言标准库在明确 comparator 下排序，再逐项比较结果。测试覆盖空串、前缀链、重复字符串、全相同长前缀、单字符、大字母表、嵌入零字节和极长字符串。

Unicode 必须先选语义：若目标是二进制键序，按 unsigned byte 比较；若是用户语言顺序，需要正规化、locale collation key 和稳定版本。不能把 UTF-8 某个字节误当完整字符，也不能在多字节序列中间切 digit。

基准除时间外记录读取字符数、重复前缀字符数、分配次数、峰值空间、页读取、连续/随机比例与 d/N。这样才能验证算法是否真的接近区分前缀下界，而不是仅在短字符串样例上更快。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“7 Sorting Strings”中先预测层级和访问模式如何改变“character work = Theta(D + n log n)”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

7 Sorting Strings

用区分前缀、基数分桶与多关键字快速排序减少字符检查

工作集所在层级

规模8192

传输256

相对成本8×

character work = Theta(D + n log n)

不变量：输出按声明字符序全序排列，公共前缀只在必要的递归层重新读取

可重放工程合同

“7 Sorting Strings”的实验必须保留：字符串集合、区分前缀 D、字符探测、桶边界、递归轨迹与排序预言机。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “7 Sorting Strings”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“character work = Theta(D + n log n)”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“终止符、字符编码或稳定性约定不一致，前缀串与长串次序被颠倒”已经修复？

本章回顾

字符串排序的成本包括指针重排与变长正文字符访问。
区分前缀总量 d 刻画必须读取的字符，下界为 Omega(d+n log n)。
MSD-first 按高位分桶，只对仍冲突的桶继续读取下一字符。
MSD 的递归树是 trie，稀疏边、哈希与路径压缩可降低结构空间。
LSD-first 必须使用稳定 digit sorter，并扫描所有位置。
r 位 digit 的 LSD 成本为 (b/r)(n+2^r)，r 约 log n 时平衡。
多关键字快排按第 i 字符三分，只有等桶推进 i，匹配比较下界。
END 哨兵处理前缀和重复串，必须小于真实字符并停止递归。
外存模型 A/B/C 对字符串可拆分能力不同，决定可达 I/O 界。