5.1 String Sorts：键索引计数、LSD、MSD与三向快排

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

学习目标

  • 能解释“5.1 · String Sorts”如何利用字符表规模与公共前缀，在键索引计数、LSD、MSD 和三向字符串快排间选择
  • 能逐项核对 字符串排序、键索引计数、低位优先字符串排序、高位优先字符串排序、三向字符串快速排序，并区分作者站内容与本页独立补充
  • 能按“LSD 固定宽字符串排序时间 Θ(WN)；MSD/三向快排成本取决于被检查字符数”手算一个最小输入，逐步检查“每次分配或切分后，已完成的字符位次序正确，元素多重集和所需稳定性保持不变”
  • 能注入“没有为字符串结束设置小于所有字符的哨兵值，导致前缀字符串排在其扩展之后”，保存基线、首个分叉、恢复和同输入重放证据

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

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

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

作者站章节坐标：5.1 · String Sorts

  • 1. 字符串排序：在本页通过“声明字符表与宽度”连接解释、交互状态和练习验收。
  • 2. 键索引计数：在本页通过“读取当前字符”连接解释、交互状态和练习验收。
  • 3. 低位优先字符串排序：在本页通过“计数或三向切分”连接解释、交互状态和练习验收。
  • 4. 高位优先字符串排序：在本页通过“递归未决区间”连接解释、交互状态和练习验收。
  • 5. 三向字符串快速排序：在本页通过“核对字典序”连接解释、交互状态和练习验收。

从“比较字符串，不必每次都从第一个字符重读”开始

Comparison sort把string当作atomic key，每次 compareTo 从左向右找first differing character。若大量strings共享长prefix，同一批字符会被反复读取。字符串排序（string sorts）直接利用key representation，把“比较两个完整对象”改成“按某个digit分组”。

先预测：数组已经按最后一个字符稳定排序，再按倒数第二个字符排序时，能否随便打乱同字符元素？不能。Equal current digit的相对顺序承载了上一轮的less-significant suffix order；一旦打乱，LSD radix sort的归纳不变量立即失效。

本节从统一的键索引计数开始，再分成两条路线：固定长度keys从least significant digit向左推进；变长strings从most significant digit向右递归。三向字符串快速排序则不用R-sized count array，而是围绕一个pivot character做less/equal/greater partition。

5.1.1 Alphabet与成本模型：R不是装饰常数

Alphabet（alphabet）提供character-to-index mapping，通常把字符映射到0至R-1。DNA的R为4，extended ASCII常取256；若直接按全部Unicode code points建立dense count array，R超过一百万，每个小subarray都清空该数组会压倒真正的数据扫描。

String sort分析需要区分三个量：

  • N：strings数量。
  • R：alphabet radix。
  • W或L：固定width，或全部strings总字符数。

“Linear”必须说明相对哪个input size。LSD固定width的成本Theta(W(N+R))；若W和R是small constants，可写成Theta(N)，但它仍读取WN个digits。MSD与three-way quicksort可能在prefix不同后停止，不一定读取每个string的全部字符。

Engineering alphabet contract还要决定“character”含义。Java charAt返回UTF-16 code unit，不等同于Unicode code point，更不等同于locale collation element。官方实现以extended ASCII R=256讲算法；真实多语言排序应先定义normalization与collation key，或把actual symbols压缩到dense ranks。

5.1.2 Key-indexed counting：四个阶段建立stable buckets

键索引计数（key-indexed counting）处理每个record带一个0至R-1 integer key的情形。它不做pairwise comparisons，而是计算每个key的bucket边界。

四阶段：

  1. Frequency：count[key + 1]++。
  2. Cumulates：prefix sum把frequencies变为bucket starts。
  3. Distribution：从左到右把record放到 aux[count[key]++]。
  4. Copy back：把aux写回a。
int[] count = new int[R + 1];
for (int i = 0; i < N; i++)
    count[key(a[i]) + 1]++;
 
for (int r = 0; r < R; r++)
    count[r + 1] += count[r];
 
for (int i = 0; i < N; i++)
    aux[count[key(a[i])]++] = a[i];
 
for (int i = 0; i < N; i++)
    a[i] = aux[i];

Frequency结束后，若 (f_r) 是key r的数量，则bucket r的initial start为：

start(r)=∑k=0r−1fk,[start(r),start(r)+fr)start(r)=\sum_{k=0}^{r-1}f_k, \qquad [start(r),start(r)+f_r)

正好是该bucket在sorted output中的half-open interval。Distribution时 count[r]从start向右移动；完成后它变成bucket end。因此需要递归边界时，应在increments前保存starts，或理解官方MSD里count array在各阶段的offset含义。

Time为Theta(N+R)，extra space为Theta(N+R)。若R远大于N，大量zero counters的初始化与prefix sum并不免费；可做alphabet compression、sparse maps，或换three-way string quicksort。

5.1.3 Stability：equal key records保留original order

稳定性（stability）来自distribution从left to right扫描input，并让每个bucket的next index单调增加。第一个见到的equal-key record先占较小position。

稳定性不是所有sorting client都需要，但LSD correctness必须依赖它。假设某一轮前array已按suffix (d+1\ldots W-1) sorted；按digit d稳定分组后：

  • Different d characters由当前digit决定顺序。
  • Equal d characters保持原relative order，所以仍按其suffix sorted。

于是array按suffix (d\ldots W-1) sorted。这是从rightmost digit向left归纳的核心。

5.1.4 LSD radix sort：固定width从右向左

低位优先字符串排序（LSD radix sort）要求所有strings长度均为W。它对 (d=W-1,W-2,\ldots,0) 各执行一次stable counting。

public static void sort(String[] a, int W) {
    int N = a.length;
    int R = 256;
    String[] aux = new String[N];
    for (int d = W - 1; d >= 0; d--) {
        int[] count = new int[R + 1];
        for (int i = 0; i < N; i++)
            count[a[i].charAt(d) + 1]++;
        for (int r = 0; r < R; r++)
            count[r + 1] += count[r];
        for (int i = 0; i < N; i++)
            aux[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
            a[i] = aux[i];
    }
}

Pass invariant可写成：

after pass d,a is sorted by substring [d,W)\text{after pass }d,\quad a\text{ is sorted by substring }[d,W)

最后d=0，substring就是whole key。算法做W轮，每轮frequency、cumulates、distribute、copy-back：

TLSD=Θ(W(N+R)),Sextra=Θ(N+R)T_{\mathrm{LSD}}=\Theta(W(N+R)), \qquad S_{\mathrm{extra}}=\Theta(N+R)

Fixed-width identifiers、dates、IP-like packed fields与machine integers适合LSD。Variable-length strings若强行pad，必须选择严格小于所有真实characters的sentinel，并承受padding width；通常MSD更自然。

32-bit signed integers不是四个普通unsigned bytes

Official LSD也把32-bit int看作四个base-256 digits。前三个bytes按0至255排序没有问题；most significant byte同时携带sign。Two's-complement negative numbers的MSB在0x80至0xFF，若按unsigned bucket放在0x00至0x7F之后，会把negative numbers排到positive之后。

最后一轮必须旋转MSB buckets，让0x80至0xFF先于0x00至0x7F；或把MSB mapping转换成signed rank。验收不能只测nonnegative样例，应覆盖minimum int、-1、0、positive及跨byte boundaries的值。

5.1.5 MSD radix sort：变长strings按prefix递归

高位优先字符串排序（MSD radix sort）先按d=0分组，随后只在same first character bucket内比较d=1，以此类推。不同prefix一旦分开，永远无需读取更后面的characters。

变长strings需要结束哨兵：

private static int charAt(String s, int d) {
    if (d == s.length()) return -1;
    return s.charAt(d);
}

令sentinel -1严格小于任何actual character，count array要容纳R+1种keys，因此官方MSD使用R+2 slots处理shifted frequencies：

private static void sort(String[] a, int lo, int hi, int d, String[] aux) {
    if (hi <= lo + CUTOFF) {
        insertion(a, lo, hi, d);
        return;
    }
    int[] count = new int[R + 2];
    for (int i = lo; i <= hi; i++)
        count[charAt(a[i], d) + 2]++;
    for (int r = 0; r < R + 1; r++)
        count[r + 1] += count[r];
    for (int i = lo; i <= hi; i++)
        aux[count[charAt(a[i], d) + 1]++] = a[i];
    for (int i = lo; i <= hi; i++)
        a[i] = aux[i - lo];
    for (int r = 0; r < R; r++)
        sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1, aux);
}

Sentinel bucket不递归：这些strings已经结束，且自然排在same-prefix longer strings之前。其余每个character bucket只在内部递归d+1。Recursive invariant是进入 sort(lo,hi,d) 时，subarray共享相同length-d prefix；完成后它按suffix from d lexicographically sorted。

MSD只读取区分keys所需的characters，但每个recursive call仍初始化R-sized counters。若data产生很多tiny buckets，大R overhead严重，所以official implementation在small subarrays切换到从digit d开始比较的insertion sort。Cutoff不是correctness条件，而是降低recursion与counter setup常数。

Worst case（N个长且几乎相同的strings）仍会读取Theta(NW) characters，并在每层付出R setup；典型成本更适合按实际examined character count C描述：

TMSD=O(C+R⋅B),T_{\mathrm{MSD}}=O(C+R\cdot B),

其中B是实际执行counting的nontrivial recursive buckets数量。这个表达揭示了R与cutoff为什么影响工程性能。

5.1.6 Three-way string quicksort：用partition避开R-sized arrays

三向字符串快速排序（three-way string quicksort）把3-way quicksort与MSD按digit推进结合起来。

private static void sort(String[] a, int lo, int hi, int d) {
    if (hi <= lo + CUTOFF) {
        insertion(a, lo, hi, d);
        return;
    }
    int lt = lo, gt = hi;
    int pivot = charAt(a[lo], d);
    int i = lo + 1;
    while (i <= gt) {
        int key = charAt(a[i], d);
        if (key < pivot) exch(a, lt++, i++);
        else if (key > pivot) exch(a, i, gt--);
        else i++;
    }
    sort(a, lo, lt - 1, d);
    if (pivot >= 0) sort(a, lt, gt, d + 1);
    sort(a, gt + 1, hi, d);
}

Partition后：

  • Less region仍在digit d递归，因为它们彼此的current characters不同。
  • Equal region只有pivot非sentinel时才进入d+1。
  • Greater region仍在digit d递归。

它不需要aux array或R counters，extra state主要是recursion stack。对small effective alphabets、大量duplicate prefixes很有吸引力；但与ordinary quicksort一样，pivot choice影响balance。Official implementation先shuffle，small subarrays切insertion sort，以降低worst-case patterns与常数。

Three-way string quicksort通常不稳定；若client要求equal full strings保持record order，需要额外策略。不要因为它按character partition，就误以为继承了key-indexed counting的stability。

5.1.7 American flag sort与in-place tradeoff

Key-indexed counting的Theta(N) aux space可通过cycle-leader placement减少。American flag sort先计算每个bucket的start/end，然后扫描每个bucket应占区间；若当前位置record属于别的bucket，就把它swap到目标bucket的next free slot，直到当前位置正确。

它保留Theta(R) counters并接近in-place，但通常不稳定，control flow也更复杂。验收必须检查每个bucket interval全部属于对应key、每个input record恰出现一次，并防止next pointer越过bucket end。对于可读性优先或需要stability的代码，普通aux distribution往往更可靠。

5.1.8 成本选择：先看input promise，再看benchmark

选择顺序：

  • Fixed-width strings、small known R、需要stable：LSD。
  • Variable strings、large N、prefix早分叉、R适中：MSD。
  • Variable strings、R很大或不想分配R-sized arrays：three-way string quicksort。
  • Tiny arrays：从known common prefix d开始的insertion sort。
  • Locale-aware text：先生成定义明确的collation keys，再对keys排序。

普通comparison sort仍有价值：它只需comparator contract，不依赖alphabet mapping，library implementation成熟。Radix方法突破comparison lower bound，是因为它使用key digits的额外结构；若digit extraction或normalization很昂贵，理论优势可能被representation cost抵消。

5.1.9 Independent certificate：sorted还不够

String sort结果至少验证三件事：

  1. Lexicographic sortedness：每个adjacent pair都满足前者不大于后者。
  2. Permutation：output与input包含完全相同的records与multiplicities。
  3. Stability（若contract要求）：equal keys的original indices严格递增。
boolean sorted = true;
for (int i = 1; i < a.length; i++)
    if (compare(a[i], a[i - 1]) < 0) sorted = false;
 
Map<Record, Integer> counts = frequencies(input);
for (Record record : output) counts.merge(record, -1, Integer::sum);
boolean permutation = counts.values().stream().allMatch(value -> value == 0);

LSD还应在每一pass检查“processed suffix sorted”；MSD应检查每个recursive bucket的shared prefix与range边界；Quick3应检查less/equal/greater partition。Local invariants能把错误定位到某一轮，而不是等最终数组失败后再猜。

Benchmark需同时记录elapsed time、allocated bytes、characters examined与input distribution。只测随机短ASCII会掩盖long common prefixes、large R、duplicates与Unicode normalization成本。

5.1.10 逐步运行路线

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

分步1 / 3

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

先在“5.1 · String Sorts”的两个最小情境间切换，再逐项选择正式概念。预测“LSD 固定宽字符串排序时间 Θ(WN)；MSD/三向快排成本取决于被检查字符数”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

5.1 · String Sorts：对象、操作与不变量

利用字符表规模与公共前缀，在键索引计数、LSD、MSD 和三向字符串快排间选择

选择最小情境

切换正式概念

输入合同操作证书algs4-5.1 · 先给前提，再执行，再验收当前概念：1/6
固定宽键
对等长日期键按日、月、年做 LSD
当前观察
string sorts：从最低有效位开始稳定排序，最后得到完整键序
LSD 固定宽字符串排序时间 Θ(WN)；MSD/三向快排成本取决于被检查字符数

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

练习与答案

练习

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

  • 字符串排序：在实验 1 中指出对应状态，并写出一个通过条件。
  • 键索引计数：在实验 2 中指出对应状态，并写出一个通过条件。
  • 低位优先字符串排序：在实验 3 中指出对应状态，并写出一个通过条件。
  • 高位优先字符串排序：在实验 1 中指出对应状态，并写出一个通过条件。
  • 三向字符串快速排序：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“LSD 固定宽字符串排序时间 Θ(WN)；MSD/三向快排成本取决于被检查字符数”不是孤立结论？

问题 3：故障恢复。 怎样证明“没有为字符串结束设置小于所有字符的哨兵值，导致前缀字符串排在其扩展之后”已经修复？

小结

  • String sorts利用characters内部结构，成本取决于N、R、width与实际examined characters。
  • Key-indexed counting通过frequency、cumulates、stable distribution与copy-back在Theta(N+R)完成small integer key排序。
  • LSD radix sort要求fixed width与stable passes，从rightmost digit向左建立sorted suffix invariant。
  • MSD radix sort从leftmost digit分buckets，用-1 sentinel让prefix string先结束，并只递归non-sentinel buckets。
  • Three-way string quicksort以pivot character划分三区，仅equal region前进到next digit，避免R-sized count arrays。
  • Independent certificate至少检查sortedness与permutation；LSD或stable client还必须检查equal-key relative order。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…