基于《算法（第4版）》第5章引言，改写为 C++ 视角，配详细中文解析与完整可运行代码。

一、为什么字符串处理如此重要？

字符串是信息的基本载体，几乎所有计算机应用都离不开字符串处理：

应用领域	具体例子
信息检索	搜索引擎关键词匹配
基因组学	DNA 序列（A、C、T、G 四字符的超长字符串）
通信系统	短信、邮件、电子书的传输与编解码
编程系统	编译器、解释器对源代码字符串的解析

---

本章将依次探讨：字符串排序、字符串查找、子串搜索（KMP 算法）、正则表达式、数据压缩。

二、C++ 中字符串的基本性质

Java 的 String 类与 C++ 的 std::string 在核心操作上有对应关系，但有几处关键差异需要注意。

2.1 字符（Character）

• Java：char 类型，16位，支持 Unicode（$2^{16}=65536$ 种可能值）
• C++：char 类型，通常 8 位；若需 Unicode 可用 char16_t 或 wchar_t
• 本章算法主要使用 ASCII（128个字符）或扩展 ASCII（256个字符），8位 char 完全够用

2.2 核心操作对比

---

操作	Java	C++ std::string	时间复杂度
声明	String s	std::string s	—
按索引取字符	s.charAt(i)	s[i] 或 s.at(i)	$O(1)$
字符串长度	s.length()	s.size() 或 s.length()	$O(1)$
提取子串	s.substring(i, j)	s.substr(i, j-i)	$O(j-i)$
拼接	s + t（用 +）	s + t 或 s.append(t)	$O(结果长度)$

---

重要差异：Java 的 substring() 是 $O(1)$（共享底层数组），C++ 的 substr() 是 $O(n)$（复制字符）。在性能敏感的代码中，C++ 应使用 string_view 来实现 $O(1)$ 的子串引用。

2.3 字符数组 vs std::string

Java 中：
  char[] a          ←→     String s
  a[i]              ←→     s.charAt(i)
  a.length          ←→     s.length()
  s.toCharArray()   ←→     转换
  new String(a)     ←→     转换
C++ 中：
  char a[]          ←→     std::string s
  a[i]              ←→     s[i]
  strlen(a)         ←→     s.size()
  std::string(a)    ←→     转换（构造函数）
  s.c_str()         ←→     转换（得到 const char*）

字符数组更省空间，但 std::string 更安全、接口更丰富。本章算法均使用 std::string，字母表大小 $R=256$。

三、字母表（Alphabet）类

3.1 为什么需要 Alphabet？

很多应用只用到有限字符集：

• DNA 序列：只有 A、C、T、G 四个字符（$R=4$）
• 二进制串：只有 0、1 两个字符（$R=2$）
• 十进制数字：0~9 十个字符（$R=10$）
  如果直接用 char（范围 0~255）做数组下标，每次都需要大小为 256 的数组。
  某些算法会创建大量这样的数组，256 倍的空间浪费是不可接受的。
  Alphabet 的作用：把任意字符集紧凑地映射到 $[0,R-1]$ 的整数区间。

3.2 Alphabet API

---

方法	作用
Alphabet(string s)	用字符串 s 中的字符创建字母表
char toChar(int i)	把索引 $i$ 转换回对应字符
int toIndex(char c)	把字符 c 转换为 $[0,R-1]$ 的索引
bool contains(char c)	字符 c 是否在字母表中
int R()	字母表大小（基数/进制数）
int lgR()	表示一个索引所需的比特数，即 $\lceil {\log }_{2}R\rceil$
vector<int> toIndices(string s)	将字符串转换为整数数组（每个元素是对应字符的索引）
string toChars(vector<int>)	将整数数组转换回字符串

---

3.3 标准字母表一览

---

名称	$R$	$\lceil {\log }_{2}R\rceil$ 位	字符集
BINARY	2	1	01
DNA	4	2	ACGT
OCTAL	8	3	01234567
DECIMAL	10	4	0123456789
HEXADECIMAL	16	4	0-9A-F
LOWERCASE	26	5	a-z
UPPERCASE	26	5	A-Z
ASCII	128	7	标准 ASCII
EXTENDED_ASCII	256	8	扩展 ASCII

---

四、字符索引数组（Character-indexed Array）

这是字符串算法中最重要的效率技巧之一。

核心思想

把字符直接当作数组下标使用：

count['A'] = 5    // 字符 A 出现了5次
count['B'] = 2    // 字符 B 出现了2次

用 Alphabet 时，先把字符转换为 $[0,R-1]$ 的整数，数组大小从 256 缩减到 $R$。

字符频率统计示意

输入: ABRACADABRA!
字母表: ABCDR
统计过程:
  A → index 0: count[0]++  (共5次)
  B → index 1: count[1]++  (共2次)
  R → index 4: count[4]++  (共2次)
  C → index 2: count[2]++  (共1次)
  D → index 3: count[3]++  (共1次)
  ! → 不在字母表中，跳过
输出:
  A 5
  B 2
  C 1
  D 1
  R 2

五、完整 C++ 实现

#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
#include <cmath>
#include <sstream>
// ============================================================
// Alphabet 类：管理有限字符集，支持字符与索引的双向映射
// ============================================================
class Alphabet {
private:
    std::string chars;          // 字母表中的所有字符（有序）
    std::vector<int> charToIdx; // 字符 → 索引的映射表（大小256，非字母表字符存-1）
    int radix;                  // 字母表大小 R
public:
    // 构造函数：传入字母表字符串，例如 "ABCDR" 或 "ACGT"
    Alphabet(const std::string& s) : charToIdx(256, -1), radix(0) {
        for (char c : s) {
            // 检查重复字符
            if (charToIdx[(unsigned char)c] != -1) {
                throw std::invalid_argument("字母表中存在重复字符");
            }
            charToIdx[(unsigned char)c] = radix; // 记录字符到索引的映射
            chars += c;                           // 记录索引到字符的映射
            radix++;
        }
    }
    // 按索引取字符：索引 i → 字符
    // 例如 toChar(0) = 'A'（对于 "ABCDR" 字母表）
    char toChar(int i) const {
        if (i < 0 || i >= radix)
            throw std::out_of_range("索引越界");
        return chars[i];
    }
    // 字符转索引：字符 c → [0, R-1] 的整数
    // 例如 toIndex('C') = 2（对于 "ABCDR" 字母表）
    int toIndex(char c) const {
        int idx = charToIdx[(unsigned char)c];
        if (idx == -1)
            throw std::invalid_argument(std::string("字符不在字母表中: ") + c);
        return idx;
    }
    // 检查字符是否在字母表中
    bool contains(char c) const {
        return charToIdx[(unsigned char)c] != -1;
    }
    // 返回字母表大小（基数 R）
    int R() const { return radix; }
    // 返回表示一个索引所需的比特数：ceil(log2(R))
    // 例如 R=4（DNA）→ lgR=2，R=256 → lgR=8
    int lgR() const {
        if (radix <= 1) return 0;
        return (int)std::ceil(std::log2(radix));
    }
    // 将字符串转换为整数数组（每个字符映射为其索引）
    // 例如 "ABRA" → {0, 1, 4, 0}（对于 "ABCDR" 字母表）
    std::vector<int> toIndices(const std::string& s) const {
        std::vector<int> result;
        result.reserve(s.size());
        for (char c : s) {
            result.push_back(toIndex(c));
        }
        return result;
    }
    // 将整数数组转换回字符串
    // 例如 {0, 1, 4, 0} → "ABRA"
    std::string toChars(const std::vector<int>& indices) const {
        std::string result;
        result.reserve(indices.size());
        for (int i : indices) {
            result += toChar(i);
        }
        return result;
    }
    // 打印字母表信息
    void print() const {
        std::cout << "字母表: \"" << chars << "\""
                  << "  R=" << radix
                  << "  lgR=" << lgR() << std::endl;
    }
};
// ============================================================
// 字符频率统计（Count 程序的 C++ 版本）
// 统计输入字符串中，字母表内各字符的出现次数
// ============================================================
void countFrequency(const Alphabet& alpha, const std::string& input) {
    int R = alpha.R();
    std::vector<int> count(R, 0); // 字符索引数组，大小为 R（而不是256）
    for (char c : input) {
        if (alpha.contains(c)) {
            // 把字符转为索引，直接作为数组下标
            count[alpha.toIndex(c)]++;
        }
        // 不在字母表中的字符（如 '!'）直接跳过
    }
    // 输出统计结果
    std::cout << "字符频率统计结果：" << std::endl;
    for (int i = 0; i < R; i++) {
        std::cout << "  " << alpha.toChar(i) << " : " << count[i] << std::endl;
    }
}
// ============================================================
// 演示 toIndices / toChars 的用法
// ============================================================
void demoConversion(const Alphabet& alpha, const std::string& s) {
    std::cout << "\n字符串与整数数组互转演示：" << std::endl;
    std::cout << "  原始字符串: \"" << s << "\"" << std::endl;
    // 过滤掉不在字母表中的字符
    std::string filtered;
    for (char c : s) {
        if (alpha.contains(c)) filtered += c;
    }
    std::cout << "  过滤后字符串: \"" << filtered << "\"" << std::endl;
    std::vector<int> indices = alpha.toIndices(filtered);
    std::cout << "  转为整数数组: {";
    for (int i = 0; i < (int)indices.size(); i++) {
        std::cout << indices[i];
        if (i + 1 < (int)indices.size()) std::cout << ", ";
    }
    std::cout << "}" << std::endl;
    std::string back = alpha.toChars(indices);
    std::cout << "  还原字符串: \"" << back << "\"" << std::endl;
}
// ============================================================
// 演示 std::string 的核心操作（对应 Java String 的常用方法）
// ============================================================
void demoStringOps() {
    std::string s = "ATTACKATDAWN";
    std::cout << "字符串基本操作演示：" << std::endl;
    std::cout << "  字符串: \"" << s << "\"" << std::endl;
    std::cout << "  长度 s.size()       = " << s.size() << std::endl;
    std::cout << "  s[3]（第4个字符）   = " << s[3] << std::endl;
    // 对应 Java 的 substring(7, 11)：从索引7开始，长度为 11-7=4
    std::string sub = s.substr(7, 4);
    std::cout << "  s.substr(7, 4)      = \"" << sub << "\"" << std::endl;
    // 拼接（时间正比于结果长度）
    std::string t = "!";
    std::string concat = s + t;
    std::cout << "  s + \"!\"            = \"" << concat << "\"" << std::endl;
    // 用 string_view 实现 O(1) 子串引用（C++17，不复制字符）
    // std::string_view sv(s.data() + 7, 4); // O(1)，类似 Java 的 substring
    std::cout << "  （C++17 可用 string_view 实现 O(1) 子串引用）" << std::endl;
}
// ============================================================
// 演示圆周率数字的字符频率统计
// ============================================================
void demoPiDigits() {
    Alphabet decimal("0123456789");
    std::string pi = "31415926535897932384626433832795028841971693993751";
    std::cout << "\n圆周率前50位数字频率统计：" << std::endl;
    std::cout << "  \"" << pi << "\"" << std::endl;
    countFrequency(decimal, pi);
}
// ============================================================
// 主程序
// ============================================================
int main() {
    // ---- 演示1：基本字符串操作 ----
    std::cout << "=== 演示1：std::string 基本操作 ===" << std::endl;
    demoStringOps();
    // ---- 演示2：Alphabet 类的创建与使用 ----
    std::cout << "\n=== 演示2：Alphabet 类 ===" << std::endl;
    Alphabet alpha("ABCDR");
    alpha.print();
    std::cout << "  toIndex('A') = " << alpha.toIndex('A') << std::endl;
    std::cout << "  toIndex('R') = " << alpha.toIndex('R') << std::endl;
    std::cout << "  toChar(2)    = " << alpha.toChar(2) << std::endl;
    std::cout << "  contains('C') = " << (alpha.contains('C') ? "true" : "false") << std::endl;
    std::cout << "  contains('Z') = " << (alpha.contains('Z') ? "true" : "false") << std::endl;
    // ---- 演示3：字符频率统计 ----
    std::cout << "\n=== 演示3：字符频率统计（Count）===" << std::endl;
    std::string input = "ABRACADABRA!";
    std::cout << "输入字符串: \"" << input << "\"" << std::endl;
    countFrequency(alpha, input);
    // ---- 演示4：字符串与整数数组互转 ----
    std::cout << "\n=== 演示4：字符串与整数数组互转 ===" << std::endl;
    demoConversion(alpha, "ABRACADABRA!");
    // ---- 演示5：DNA 字母表 ----
    std::cout << "\n=== 演示5：DNA 字母表 ===" << std::endl;
    Alphabet dna("ACGT");
    dna.print();
    std::string seq = "ACGTACGT";
    std::cout << "DNA 序列: \"" << seq << "\"" << std::endl;
    auto idx = dna.toIndices(seq);
    std::cout << "整数表示: {";
    for (int i = 0; i < (int)idx.size(); i++) {
        std::cout << idx[i];
        if (i + 1 < (int)idx.size()) std::cout << ",";
    }
    std::cout << "}" << std::endl;
    // ---- 演示6：圆周率数字统计 ----
    std::cout << "\n=== 演示6：圆周率数字频率统计 ===" << std::endl;
    demoPiDigits();
    return 0;
}

https://godbolt.org/z/qcc6GYqsv

六、关键概念图解

字母表映射关系（以 “ABCDR” 为例）

字符集:   A   B   C   D   R
           |   |   |   |   |
索引:      0   1   2   3   4
charToIdx[] 数组（大小256）:
  下标  65('A') → 0
  下标  66('B') → 1
  下标  67('C') → 2
  下标  68('D') → 3
  下标  82('R') → 4
  其余所有下标   → -1（不在字母表中）
chars 数组（大小R=5）:
  index: 0  1  2  3  4
  char:  A  B  C  D  R

字符索引数组的优势

不用 Alphabet（朴素方案）:
  count 数组大小 = 256（扩展ASCII全集）
  浪费内存：大量下标永远不会被用到
使用 Alphabet（R=4 的 DNA 字母表）:
  count 数组大小 = 4
  节省了 256/4 = 64 倍的空间
某些算法需要创建 O(N) 个这样的数组，
空间节省从"省事"变成"生死攸关"。

字符串操作时间复杂度对比

七、基数（Radix）与进制的关系

字母表大小 $R$ 就是这个字符集的进制数（基数）。

字母表	$R$	含义
BINARY	2	二进制，每个字符需 $\lceil {\log }_{2}2\rceil =1$ 位
DNA	4	四进制，每个字符需 $\lceil {\log }_{2}4\rceil =2$ 位
DECIMAL	10	十进制，每个字符需 $\lceil {\log }_{2}10\rceil =4$ 位
ASCII	128	128进制，每个字符需 $\lceil {\log }_{2}128\rceil =7$ 位
EXTENDED_ASCII	256	256进制，每个字符需 $\lceil {\log }_{2}256\rceil =8$ 位

---

lgR() 方法返回的正是 $\lceil {\log }_{2}R\rceil$，即表示一个字符所需的最少比特数。
在后续的基数排序（Radix Sort）等算法中，$R$ 作为"进制"直接影响算法的分组方式和时间复杂度分析。

八、关于 C++ 实现的额外说明

为什么本章用 std::string 而不是 char[]？

原书 Java 代码主要用 String，对应 C++ 的 std::string。两者在接口设计上最为接近。
对于性能极端敏感的场合：

• 用 char[]（或 const char*）替代 std::string，可以避免堆分配。
• 用 std::string_view（C++17）替代 substr()，实现 $O(1)$ 子串引用。

字母表大小的选择

本章大多数算法以 $R=256$（扩展 ASCII）为默认值，在代码中写死。分析时将 $R$ 作为参数，讨论对任意字母表的推广。

九、章节路线图

第5章 字符串处理
├── 5.1 字符串排序
│     ├── 键索引计数法（Radix 思想的基础）
│     ├── 低位优先（LSD）基数排序
│     └── 高位优先（MSD）基数排序
├── 5.2 单词查找树（Trie）
│     └── 字符串作为键的符号表
├── 5.3 子串搜索
│     ├── 暴力匹配
│     ├── KMP 算法
│     ├── Boyer-Moore 算法
│     └── Rabin-Karp 指纹算法
├── 5.4 正则表达式
│     └── 非确定性有限自动机（NFA）
└── 5.5 数据压缩
      ├── 游程编码
      ├── 霍夫曼编码
      └── LZW 压缩

核心思想一句话总结：字符串算法的效率核心在于"把字符直接当数组下标用"——通过 Alphabet 类把字符集紧凑映射到 $[0,R-1]$，以 $O(1)$ 时间完成字符到索引的转换，从而将字符串问题转化为高效的整数数组操作。

字符串排序：键索引计数法（Key-Indexed Counting）

基于《算法（第4版）》5.1节，改写为 C++ 视角，配详细中文解析与完整可运行代码。

一、字符串排序的两大流派

在开始键索引计数法之前，先了解字符串排序的整体脉络：

流派	方向	别名	特点
从右到左按字符排序	低位优先	LSD（Least Significant Digit）	适合等长字符串
从左到右按字符排序	高位优先	MSD（Most Significant Digit）	不需检查所有字符

---

键索引计数法是这两种方法的共同基础，先理解它，后面的排序算法就水到渠成。

二、问题引入：按小整数键排序

场景

一位老师维护着一个班级名单，每位学生属于某个小组（编号 1、2、3、4……），需要将学生按小组编号排序。
关键特点：排序的键是范围很小的整数（例如 0 到 R-1）。

学生	小组
Anderson	2
Brown	3
Davis	3
Garcia	4
Harris	1
Jackson	3
Johnson	4
Jones	3
Martin	1
Martinez	2
Miller	2
Moore	1
Robinson	2
Smith	4
Taylor	3
Thomas	4
Thompson	4
White	2
Williams	3
Wilson	4

---

排序目标：按小组编号从小到大排列，相同小组内保持原顺序（稳定排序）。

三、核心思路：四步走

键索引计数法分为四个步骤，环环相扣。用一个 count[] 数组贯穿始终。

数组定义：count[r+1] = 键值为 r 的元素个数
          （注意是 r+1，原因见步骤一）
大小：count[R+1]，R 为键值范围（本例 R=5，小组编号 0~4）

步骤一：统计频率（Compute Frequency Counts）

对每个元素，将其键值 $r$ 对应的 count[r+1] 加一。
为什么是 count[r+1] 而不是 count[r]？
这是一个巧妙的"错位"技巧——把频率存在"右移一位"的位置，这样步骤二的累加结果就直接变成了起始索引，不需要再额外偏移。

初始：count = [0, 0, 0, 0, 0, 0]
               ↑  ↑  ↑  ↑  ↑  ↑
            idx:0  1  2  3  4  5
                   (count[r+1])
处理 Anderson(组2)：count[3]++  → [0, 0, 0, 1, 0, 0]
处理 Brown(组3)：  count[4]++  → [0, 0, 0, 1, 1, 0]
处理 Davis(组3)：  count[4]++  → [0, 0, 0, 1, 2, 0]
...（处理完所有20名学生）
最终：count = [0, 0, 3, 5, 6, 6]
              组0  组1  组2  组3  组4
              0个  0个→ 3个  5个  6个  6个（错位存储）

处理完所有学生后，count[r+1] 表示键值等于 $r$ 的元素有多少个：
$$\text{count}[r+1]=\text{键值为 }r\text{ 的元素数量}$$

步骤二：频率转起始索引（Transform Counts to Indices）

对 count[] 做前缀和，将频率转换为每组在输出数组中的起始位置：
$$\text{count}[r]+=\text{count}[r-1]\text{（从左到右累加）}$$

累加前：count = [0, 0, 3, 5, 6, 6]
               组0起 组1起 组2起 组3起 组4起
                 0    0    3    8   14   20
累加过程（count[r+1] += count[r]）：
  r=0: count[1] += count[0] → count[1] = 0
  r=1: count[2] += count[1] → count[2] = 3
  r=2: count[3] += count[2] → count[3] = 8
  r=3: count[4] += count[3] → count[4] = 14
  r=4: count[5] += count[4] → count[5] = 20
累加后：count = [0, 0, 3, 8, 14, 20]

现在 count[r] 的含义变为：键值为 $r$ 的元素应该放在输出数组的起始位置。

小组	起始位置 count[r]	该组元素个数
1	count[1] = 0	3
2	count[2] = 3	5
3	count[3] = 8	6
4	count[4] = 14	6

---

步骤三：分配数据（Distribute the Data）

按原数组顺序，将每个元素放到 aux[]（辅助数组）的正确位置：

• 取元素的键值 $r$
• 将元素放到 aux[count[r]]
• 然后 count[r]++（下一个键值为 $r$ 的元素放在下一格）
  这个"放一个、指针前移一格"的机制保证了稳定性：原数组中先出现的元素，在同组内也先出现。

分配 Harris(组1)：aux[count[1]] = aux[0] = Harris,  count[1] → 1
分配 Martin(组1)：aux[count[1]] = aux[1] = Martin,  count[1] → 2
分配 Moore(组1)： aux[count[1]] = aux[2] = Moore,   count[1] → 3
分配 Anderson(组2)：aux[count[2]] = aux[3] = Anderson, count[2] → 4
...

步骤四：回写原数组（Copy Back）

将 aux[] 中已排好序的数据复制回原数组 a[]。

四、完整流程 ASCII 演示

原始数组 a[] (N=20):
idx: 0          1       2       3       4       5
     Anderson/2 Brown/3 Davis/3 Garcia/4 Harris/1 ...
步骤一：统计频率（count[r+1]++）
count: [0, 0, 3, 5, 6, 6]
              ↑  ↑  ↑  ↑
           组1=3 组2=5 组3=6 组4=6
步骤二：前缀累加（转起始索引）
count: [0, 0, 3, 8, 14, 20]
           ↑  ↑   ↑   ↑
         组1从0 组2从3 组3从8 组4从14
步骤三：分配到 aux[]
aux[0..2]   = 组1的元素（Harris, Martin, Moore）
aux[3..7]   = 组2的元素（Anderson, Martinez, Miller, Robinson, White）
aux[8..13]  = 组3的元素（Brown, Davis, Jackson, Jones, Taylor, Williams）
aux[14..19] = 组4的元素（Garcia, Johnson, Smith, Thomas, Thompson, Wilson）
步骤四：复制回 a[]
a[] = aux[]（已排好序）

五、四步骤的 Mermaid 流程图

六、完整 C++ 实现

#include <iostream>
#include <string>
#include <vector>
// ============================================================
// 学生记录：包含姓名和小组编号
// ============================================================
struct Student {
    std::string name;
    int section; // 小组编号，范围 [0, R)
    int key() const { return section; } // 统一接口：返回排序键
};
// ============================================================
// 键索引计数排序
// 要求：a[i].key() 返回 [0, R) 范围内的整数
// 时间复杂度：O(N + R)
// 空间复杂度：O(N + R)
// 稳定性：稳定（相同键的元素保持原有相对顺序）
// ============================================================
void keyIndexedCounting(std::vector<Student>& a, int R) {
    int N = (int)a.size();
    std::vector<Student> aux(N);   // 辅助数组，用于暂存排序结果
    std::vector<int> count(R + 1, 0); // count[r+1] = 键值为 r 的元素个数
                                       // 大小为 R+1，多一格是"错位"技巧的需要
    // ---- 步骤一：统计频率 ----
    // 对每个元素，将键值 r 对应的 count[r+1] 加一
    // 注意：存到 r+1 而不是 r，这样步骤二的累加结果直接就是起始索引
    for (int i = 0; i < N; i++) {
        count[a[i].key() + 1]++;
    }
    // ---- 步骤二：频率转起始索引（前缀累加） ----
    // 执行后：count[r] = 键值为 r 的元素在 aux[] 中的起始放置位置
    // 例如：count[3]=8 表示键值为3的元素从 aux[8] 开始放
    for (int r = 0; r < R; r++) {
        count[r + 1] += count[r];
    }
    // ---- 步骤三：分配数据（核心步骤，保证稳定性） ----
    // 按原始顺序扫描 a[]，将每个元素放到 aux[] 的正确位置
    // count[key] 是当前键值的下一个可用位置，放完后指针前移一格
    for (int i = 0; i < N; i++) {
        int key = a[i].key();
        aux[count[key]++] = a[i]; // 放到正确位置，然后该组指针后移
    }
    // ---- 步骤四：复制回原数组 ----
    for (int i = 0; i < N; i++) {
        a[i] = aux[i];
    }
}
// ============================================================
// 打印学生数组
// ============================================================
void printStudents(const std::vector<Student>& a, const std::string& title) {
    std::cout << title << std::endl;
    for (const auto& s : a) {
        std::cout << "  " << s.name;
        // 对齐格式
        int pad = 12 - (int)s.name.size();
        for (int i = 0; i < pad; i++) std::cout << ' ';
        std::cout << "组" << s.section << std::endl;
    }
    std::cout << std::endl;
}
// ============================================================
// 演示四步骤的中间状态
// ============================================================
void demoSteps(std::vector<Student>& a, int R) {
    int N = (int)a.size();
    std::vector<int> count(R + 1, 0);
    // 步骤一
    for (int i = 0; i < N; i++) count[a[i].key() + 1]++;
    std::cout << "步骤一（统计频率后 count[]）：" << std::endl;
    std::cout << "  idx: ";
    for (int r = 0; r <= R; r++) std::cout << r << "  ";
    std::cout << std::endl << "  val: ";
    for (int r = 0; r <= R; r++) std::cout << count[r] << "  ";
    std::cout << std::endl << std::endl;
    // 步骤二
    for (int r = 0; r < R; r++) count[r + 1] += count[r];
    std::cout << "步骤二（前缀累加后 count[]，即各组起始位置）：" << std::endl;
    std::cout << "  idx: ";
    for (int r = 0; r <= R; r++) std::cout << r << "   ";
    std::cout << std::endl << "  val: ";
    for (int r = 0; r <= R; r++) {
        std::cout << count[r];
        if (count[r] < 10) std::cout << "  ";
        else std::cout << " ";
    }
    std::cout << std::endl;
    std::cout << "  解读：键值1从位置" << count[1]
              << "开始，键值2从位置" << count[2]
              << "开始，键值3从位置" << count[3]
              << "开始，键值4从位置" << count[4] << "开始" << std::endl;
    std::cout << std::endl;
    // 步骤三
    std::vector<Student> aux(N);
    for (int i = 0; i < N; i++) {
        int key = a[i].key();
        aux[count[key]++] = a[i];
    }
    std::cout << "步骤三（分配后 aux[]）：" << std::endl;
    for (int i = 0; i < N; i++) {
        std::cout << "  aux[" << i << "] = "
                  << aux[i].name << " (组" << aux[i].section << ")" << std::endl;
    }
    std::cout << std::endl;
    // 步骤四
    for (int i = 0; i < N; i++) a[i] = aux[i];
}
// ============================================================
// 主程序
// ============================================================
int main() {
    // 原始数据（按文档中的顺序）
    std::vector<Student> students = {
        {"Anderson",  2}, {"Brown",    3}, {"Davis",    3},
        {"Garcia",    4}, {"Harris",   1}, {"Jackson",  3},
        {"Johnson",   4}, {"Jones",    3}, {"Martin",   1},
        {"Martinez",  2}, {"Miller",   2}, {"Moore",    1},
        {"Robinson",  2}, {"Smith",    4}, {"Taylor",   3},
        {"Thomas",    4}, {"Thompson", 4}, {"White",    2},
        {"Williams",  3}, {"Wilson",   4}
    };
    int R = 5; // 键值范围：组号 0~4（组0无人，组1~4有人）
    printStudents(students, "=== 排序前（原始顺序）===");
    // 详细演示四步骤
    std::cout << "=== 四步骤详细演示 ===" << std::endl << std::endl;
    demoSteps(students, R);
    printStudents(students, "=== 排序后（按小组编号）===");
    // ---- 验证稳定性 ----
    std::cout << "=== 验证稳定性 ===" << std::endl;
    std::cout << "组1（Harris、Martin、Moore）：原始相对顺序是否保持？" << std::endl;
    for (const auto& s : students) {
        if (s.section == 1)
            std::cout << "  " << s.name << std::endl;
    }
    // 原始顺序中 Harris(idx=4) < Martin(idx=8) < Moore(idx=11)，排序后应保持此顺序
    std::cout << std::endl;
    // ---- 用纯整数键演示（更简洁） ----
    std::cout << "=== 纯整数键版本演示 ===" << std::endl;
    // 用 int 数组模拟键值，展示核心逻辑
    std::vector<int> keys = {2, 3, 3, 4, 1, 3, 4, 3, 1, 2, 2, 1, 2, 4, 3, 4, 4, 2, 3, 4};
    int n = (int)keys.size();
    int r = 5;
    std::vector<int> cnt(r + 1, 0);
    std::vector<int> out(n);
    for (int i = 0; i < n; i++) cnt[keys[i] + 1]++;
    for (int j = 0; j < r; j++) cnt[j + 1] += cnt[j];
    for (int i = 0; i < n; i++) out[cnt[keys[i]]++] = keys[i];
    std::cout << "输入键: ";
    for (int k : keys) std::cout << k << " ";
    std::cout << std::endl;
    std::cout << "排序后: ";
    for (int k : out)  std::cout << k << " ";
    std::cout << std::endl;
    return 0;
}

七、关键步骤图解

"错位存储"技巧的原理

如果直接 count[r]++（不错位）：
  统计后：count[1]=3, count[2]=5, count[3]=6, count[4]=6
  要求起始索引：
    组1起始 = 0
    组2起始 = 3      （= count[1]）
    组3起始 = 3+5=8  （= count[1]+count[2]）
    组4起始 = 3+5+6=14
  还需要额外偏移计算，不够优雅。
如果 count[r+1]++（错位一格）：
  统计后：count[2]=3, count[3]=5, count[4]=6, count[5]=6
  前缀累加后：count = [0, 0, 3, 8, 14, 20]
  此时 count[r] 直接就是键值 r 的起始索引！
  零额外计算，一举两得。

分配步骤的"指针前移"机制

初始 count（前缀累加后）：
  count[1]=0, count[2]=3, count[3]=8, count[4]=14
扫描原数组（按原顺序）：
  Anderson(组2) → aux[count[2]] = aux[3], count[2] → 4
  Brown(组3)    → aux[count[3]] = aux[8], count[3] → 9
  Davis(组3)    → aux[count[3]] = aux[9], count[3] → 10
  Garcia(组4)   → aux[count[4]] = aux[14], count[4] → 15
  Harris(组1)   → aux[count[1]] = aux[0], count[1] → 1
  ...
"先放、后移"保证：
  同一组内，原数组中靠前的元素，在 aux[] 中也靠前 → 稳定性！

八、复杂度分析

命题 A：键索引计数法使用
$$8N+3R+1$$
次数组访问，对 $N$ 个键值在 $[0,R-1]$ 范围内的元素进行稳定排序。
各步骤数组访问次数详细统计：

步骤	操作	数组访问次数
初始化 count[]	全部置 0	$R+1$ 次
步骤一：统计频率	读 key，写 count[r+1]	$2N$ 次
步骤二：前缀累加	读写 count[]	$2R$ 次
步骤三：分配数据	读 key，读写 count[r]，写 aux[]	$3N$ 次
步骤四：复制回原数组	读 aux[]，写 a[]	$2N$ 次
合计		$8N+3R+1$ 次

---

为什么能突破 $N\log N$ 的下界？

基于比较的排序算法，最坏情况下需要
$$\Omega (N\log N)$$
次比较（这是信息论下界，见第2章命题 I）。
键索引计数法完全不进行元素间的比较，只通过 key() 直接获取键值作为整数下标。因此它不受 $N\log N$ 下界的约束。
当 $R=O(N)$ 时（键值范围与元素数量同阶），总复杂度为：
$$O(8N+3R)=O(N)$$
这是线性时间排序！

九、字符串排序中的应用

键索引计数法在字符串排序中的应用：把字符当作键。
字符的 ASCII 值本身就是 $[0,255]$ 范围内的整数，完美符合键索引计数法的要求。

字符串排序中：
  R = 256（扩展 ASCII）
  key = 字符串中某一位的字符值
键索引计数法 → LSD 排序（从右到左，对每一位做一次键索引计数）
             → MSD 排序（从左到右，递归分组）

LSD 排序的思路预览

待排序（4位等长字符串）：
  BCDA  ABCD  DCBA  CDAB
第4位（最低位）排序：
  ABCD  BCDA  DCBA  CDAB
第3位排序：
  ABCD  CDAB  BCDA  DCBA
第2位排序：
  ABCD  BCDA  CDAB  DCBA
第1位（最高位）排序：
  ABCD  BCDA  CDAB  DCBA
（每次排序使用键索引计数法，保证稳定性）

十、与常见排序算法的比较

---

算法	时间复杂度	空间	稳定	适用场景
归并排序	$O(N\log N)$	$O(N)$	是	通用
快速排序	$O(N\log N)$ 期望	$O(\log N)$	否	通用，实践最快
堆排序	$O(N\log N)$	$O(1)$	否	原地，不稳定
键索引计数	$O(N+R)$	$O(N+R)$	是	键为小整数
LSD 基数排序	$O(W\cdot (N+R))$	$O(N+R)$	是	等长字符串

---

其中 $W$ 为字符串长度，$R$ 为字母表大小。

核心思想一句话总结：键索引计数法用"错位存储频率→前缀累加→按原顺序分配"的三步技巧，将键值直接变成数组下标，完全绕过元素比较，在 $O(N+R)$ 线性时间内完成稳定排序，是 LSD/MSD 字符串排序的基石。

LSD 字符串排序（低位优先基数排序）

基于《算法（第4版）》5.1节，改写为 C++ 视角，配详细中文解析与完整可运行代码。

一、什么是 LSD 排序？

LSD（Least Significant Digit，最低位优先）字符串排序的核心思想：

把字符串看成一个 $R$ 进制数（$R$ 为字母表大小），从右到左逐位对整个数组做一次稳定的键索引计数排序，共做 $W$ 次（$W$ 为字符串长度）。

典型应用场景

• 车牌号排序（固定长度，如 4PGC938）
• 电话号码排序
• 银行账号排序
• IP 地址排序
  这些应用的共同特点：所有字符串长度相同，即 $W$ 固定。

二、算法思路

为什么从右到左？

直觉上，我们会觉得应该从最重要的位（最左边）开始排序。但 LSD 偏偏反过来——从最不重要的位（最右边）开始。
关键在于：稳定排序的"记忆"效应。

考虑两个字符串：
  BA
  AB
第1轮（按最后一位排序）：
  AB（B < ... 等等，先看最后一位）
  最后一位：A→0, B→1
  排序后：BA  AB
  （BA 的最后一位 A < AB 的最后一位 B）
第2轮（按第一位排序，稳定）：
  第一位：A<B
  AB 排在 BA 前面
  最终：AB  BA
正确！

关键规律：

• 如果两个字符串在当前位上不同，当前这轮排序就确定了它们的顺序。
• 如果两个字符串在当前位上相同，由于排序是稳定的，它们保持之前几轮已经确定的相对顺序。

三、正确性证明（命题 B）

命题 B：LSD 字符串排序能对等长字符串进行稳定排序。
归纳证明（从右往左，第 $i$ 轮结束后）：
经过 $i$ 轮排序后，任意两个字符串 $s$、$t$ 在"最后 $i$ 位"这个视角下，一定已经按正确顺序排列。
分两种情况：

• 若 $s$ 和 $t$ 的第 $i$ 位不同：当前这轮直接排好了顺序，后续（更高位的）排序因为稳定性不会破坏这个顺序。
• 若 $s$ 和 $t$ 的第 $i$ 位相同：当前这轮不改变它们的相对顺序，而由归纳假设知之前 $i-1$ 轮已经正确排好了更低位，所以整体顺序也正确。

四、算法步骤详解（以车牌为例）

输入数据（W=7）

4PGC938
2IYE230
3CIO720
1ICK750
1OHV845
4JZY524
1ICK750
3CIO720
1OHV845
1OHV845
2RLA629
2RLA629
3ATW723

每一轮排序过程（从右到左，d=6 到 d=0）

原始输入（d=6，对最后一位 8,0,0,0,5,4,0,0,5,5,9,9,3 排序）:
  4PGC938  2IYE230  3CIO720  1ICK750  1OHV845
  4JZY524  1ICK750  3CIO720  1OHV845  1OHV845
  2RLA629  2RLA629  3ATW723
d=6 排序后（按最后一个字符）:
  2IYE230  3CIO720  1ICK750  3CIO720  4JZY524
  3ATW723  1ICK750  4PGC938  1OHV845  1OHV845
  1OHV845  2RLA629  2RLA629
d=5 排序后（按倒数第二个字符）:
  ...（每轮都是完整的键索引计数排序）
d=0 排序后（按第一个字符，最后一轮）:
  1ICK750  1ICK750  1OHV845  1OHV845  1OHV845
  2IYE230  2RLA629  2RLA629  3ATW723  3CIO720
  3CIO720  4JZY524  4PGC938

完整的逐位排序过程（每列是一轮排序后的结果）：

input    d=6      d=5      d=4      d=3      d=2      d=1      d=0(输出)
4PGC938  2IYE230  3CIO720  3CIO720  1ICK750  1ICK750  1ICK750  1ICK750
2IYE230  3CIO720  3CIO720  1ICK750  1ICK750  1OHV845  1ICK750  1ICK750
3CIO720  1ICK750  3ATW723  4JZY524  1OHV845  1OHV845  1OHV845  1OHV845
1ICK750  3CIO720  4JZY524  2IYE230  1OHV845  1OHV845  1OHV845  1OHV845
1OHV845  4JZY524  1ICK750  3ATW723  1OHV845  3ATW723  1OHV845  1OHV845
4JZY524  3ATW723  1ICK750  4PGC938  4JZY524  2IYE230  2IYE230  2IYE230
1ICK750  1ICK750  4PGC938  2RLA629  2IYE230  2RLA629  2RLA629  2RLA629
3CIO720  4PGC938  1OHV845  2RLA629  2RLA629  2RLA629  2RLA629  2RLA629
1OHV845  1OHV845  1OHV845  1OHV845  2RLA629  4JZY524  3ATW723  3ATW723
1OHV845  1OHV845  1OHV845  1OHV845  3ATW723  3CIO720  3CIO720  3CIO720
2RLA629  1OHV845  2RLA629  3CIO720  3CIO720  3CIO720  3CIO720  3CIO720
2RLA629  2RLA629  2RLA629  3CIO720  3CIO720  4PGC938  4JZY524  4JZY524
3ATW723  2RLA629  2IYE230  1OHV845  4PGC938  1ICK750  4PGC938  4PGC938

五、Mermaid 流程图

六、完整 C++ 实现

#include <iostream>
#include <string>
#include <vector>
// ============================================================
// LSD 字符串排序
// 对 N 个长度均为 W 的字符串进行排序
// 字母表大小 R = 256（扩展 ASCII）
// ============================================================
void lsdSort(std::vector<std::string>& a, int W) {
    int N = (int)a.size();
    const int R = 256;                     // 字母表大小（扩展 ASCII）
    std::vector<std::string> aux(N);       // 辅助数组，大小与原数组相同
                                           // 注意：只初始化一次，不是每轮都重建
    // 从最右边的字符（第 W-1 位）开始，逐位向左排序
    for (int d = W - 1; d >= 0; d--) {
        // ---- 步骤一：统计第 d 位字符的频率 ----
        // count[c+1]++ 表示字符值为 c 的字符串数量加一
        // 使用"错位"技巧（存到 c+1），方便步骤二直接得到起始索引
        std::vector<int> count(R + 1, 0);
        for (int i = 0; i < N; i++) {
            unsigned char c = (unsigned char)a[i][d]; // 取第 d 位字符
            count[c + 1]++;                            // 错位存储
        }
        // ---- 步骤二：频率转起始索引（前缀累加） ----
        // 执行后：count[c] = 字符值为 c 的字符串在 aux[] 中的起始位置
        for (int r = 0; r < R; r++) {
            count[r + 1] += count[r];
        }
        // ---- 步骤三：按第 d 位字符将字符串分配到 aux[] ----
        // 按原始顺序扫描（保证稳定性：相同字符的字符串保持原有相对顺序）
        for (int i = 0; i < N; i++) {
            unsigned char c = (unsigned char)a[i][d];
            aux[count[c]++] = a[i]; // 放到正确位置，当前组的指针后移一格
        }
        // ---- 步骤四：将排好序的结果复制回原数组 ----
        for (int i = 0; i < N; i++) {
            a[i] = aux[i];
        }
    }
}
// ============================================================
// 打印字符串数组
// ============================================================
void printArray(const std::vector<std::string>& a, const std::string& title) {
    std::cout << title << std::endl;
    for (int i = 0; i < (int)a.size(); i++) {
        std::cout << "  [" << i << "] " << a[i] << std::endl;
    }
    std::cout << std::endl;
}
// ============================================================
// 验证数组是否已排序
// ============================================================
bool isSorted(const std::vector<std::string>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        if (a[i] < a[i - 1]) return false;
    }
    return true;
}
// ============================================================
// 演示：逐轮打印中间状态
// ============================================================
void lsdSortVerbose(std::vector<std::string> a, int W) {
    int N = (int)a.size();
    const int R = 256;
    std::vector<std::string> aux(N);
    std::cout << "=== 逐轮排序过程 ===" << std::endl;
    std::cout << "初始: ";
    for (auto& s : a) std::cout << s << "  ";
    std::cout << std::endl << std::endl;
    for (int d = W - 1; d >= 0; d--) {
        std::vector<int> count(R + 1, 0);
        // 步骤一
        for (int i = 0; i < N; i++)
            count[(unsigned char)a[i][d] + 1]++;
        // 步骤二
        for (int r = 0; r < R; r++)
            count[r + 1] += count[r];
        // 步骤三
        for (int i = 0; i < N; i++) {
            unsigned char c = (unsigned char)a[i][d];
            aux[count[c]++] = a[i];
        }
        // 步骤四
        for (int i = 0; i < N; i++) a[i] = aux[i];
        // 打印本轮结果
        std::cout << "d=" << d << " (按第" << (d + 1) << "位排序后): ";
        for (auto& s : a) std::cout << s << "  ";
        std::cout << std::endl;
    }
    std::cout << std::endl;
}
// ============================================================
// 主程序
// ============================================================
int main() {
    // ---- 测试1：车牌号排序 ----
    std::cout << "=== 测试1：车牌号 LSD 排序（W=7）===" << std::endl;
    std::vector<std::string> plates = {
        "4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845",
        "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845",
        "2RLA629", "2RLA629", "3ATW723"
    };
    int W = 7;
    printArray(plates, "排序前：");
    lsdSortVerbose(plates, W);  // 逐轮演示
    // 再次排序（lsdSortVerbose 内部用了副本，这里重新对原数组排序）
    std::vector<std::string> plates2 = {
        "4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845",
        "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845",
        "2RLA629", "2RLA629", "3ATW723"
    };
    lsdSort(plates2, W);
    printArray(plates2, "排序后：");
    std::cout << "验证有序：" << (isSorted(plates2) ? "通过" : "失败") << std::endl;
    std::cout << std::endl;
    // ---- 测试2：纯数字字符串 ----
    std::cout << "=== 测试2：电话号码排序（W=8）===" << std::endl;
    std::vector<std::string> phones = {
        "13812345", "13598765", "15987654", "13812345",
        "18923456", "13599999", "15012345"
    };
    W = 8;
    printArray(phones, "排序前：");
    lsdSort(phones, W);
    printArray(phones, "排序后：");
    std::cout << "验证有序：" << (isSorted(phones) ? "通过" : "失败") << std::endl;
    std::cout << std::endl;
    // ---- 测试3：纸牌排序演示（先按点数后按花色）----
    // 用2字符字符串表示：第1位=花色(C/D/H/S)，第2位=点数(1-9,T,J,Q,K)
    // LSD: 先按第2位（点数）排，再按第1位（花色）排
    std::cout << "=== 测试3：纸牌 LSD 排序 ===" << std::endl;
    std::cout << "（格式：花色+点数，C=梅,D=方,H=红,S=黑）" << std::endl;
    std::vector<std::string> cards = {
        "S5", "H3", "CA", "D7", "HK", "CQ", "S2",
        "DJ", "H5", "C3", "DA", "S9", "HJ", "D5"
    };
    W = 2;
    printArray(cards, "排序前：");
    lsdSort(cards, W);
    printArray(cards, "排序后（先花色后点数）：");
    std::cout << "验证有序：" << (isSorted(cards) ? "通过" : "失败") << std::endl;
    return 0;
}

https://godbolt.org/z/64arYh3Pe

七、稳定性为何如此关键？

设想去掉稳定性会发生什么：

假设用不稳定的排序（比如选择排序）替代键索引计数排序：
原始数组：
  "BA"
  "AB"
  "AA"
第1轮（按最后一位，不稳定）：
  "BA" 和 "AA" 最后一位都是 A
  若顺序被随机打乱：可能变成 "AA"  "BA"  "AB"
第2轮（按第一位，不稳定）：
  "AA" 和 "AB" 第一位都是 A
  若顺序再被打乱：可能变成 "AB"  "AA"  "BA"
最终结果 "AB" "AA" "BA"——错误！
应该是 "AA" "AB" "BA"。

稳定性的保证：当第 $d$ 轮排序完成后，对于第 $d$ 位相同的字符串，它们已经按照第 $d+1,d+2,\dots ,W-1$ 位排好的顺序被"冻结"，后续轮次不会破坏这个顺序。

八、LSD 的历史：打孔卡片机

LSD 基数排序的思想来自 20 世纪初的打孔卡片排序机，早于计算机数十年：

打孔卡片机排序流程：
  1. 操作员将一叠卡片送入机器，选择最右边一列的孔位
  2. 机器将卡片分发到 10 个槽（对应数字 0~9）
  3. 操作员按顺序收集各槽的卡片（稳定的物理叠放）
  4. 对下一列重复上述过程，直到最左列
"物理叠放"保证了稳定性，这正是键索引计数排序所模拟的过程。

扑克牌排序类比：

要给一副扑克牌排序（先按花色，花色内按点数）：
LSD 做法（两轮）：
  第1轮：按点数分成13堆，按顺序收起（A,2,3,...,K）
  第2轮：按花色分成4堆（梅花,方块,红心,黑桃），按顺序收起
由于第2轮按顺序收堆时，同花色内部点数已经排好且不再被打乱
→ 最终结果：按花色排列，同花色内按点数排列

九、复杂度分析

命题 B（续）：LSD 字符串排序使用
$$\sim 7WN+3WR$$
次数组访问，额外空间正比于 $N+R$，可对 $N$ 个长度为 $W$、字母表大小为 $R$ 的字符串进行排序。
推导：
共进行 $W$ 轮键索引计数排序，每轮访问次数由命题 A 给出为 $8N+3R$（辅助数组 aux[] 只初始化一次，节省一次 $N$ 的初始化）：
$$\text{总访问次数}\approx W\times (7N+3R)=7WN+3WR$$

参数	典型值	对总时间的影响
$N$（字符串数量）	百万级	主导项 $7WN$
$W$（字符串长度）	固定常数	常数倍
$R$（字母表大小）	256	当 $R\ll N$ 时可忽略
线性时间：当 $R=O(N)$ 时，总时间为
$$
O(WN)
$$
由于输入总字符数为 $WN$，所以 LSD 排序的时间正比于输入大小，是线性时间算法。
这意味着：无论 $N$ 多大，只要字符串长度 $W$ 固定，LSD 排序就能在线性时间内完成。

十、LSD vs 通用排序算法对比

算法	时间复杂度	是否比较元素	适用条件
归并排序	$O(WN\log N)$	是（最多比较 $W$ 字符）	通用
快速排序	$O(WN\log N)$ 期望	是	通用
LSD 基数排序	$O(WN)$	否（只看单个字符）	等长字符串
LSD 能打败 $O(N\log N)$ 下界的原因：
$N\log N$ 是基于比较排序的下界（信息论证明，见第2章）。LSD 不做字符串间的比较，只通过字符的整数值做数组下标，所以不受此约束。

十一、局限性与扩展

局限：只适合等长字符串

车牌、电话号码、IP 地址适合 LSD。但如果字符串长度不同（如英语单词），LSD 需要额外处理（补齐到最长长度），效率下降。

扩展：变长字符串用 MSD

MSD（高位优先）排序从左到右处理，天然支持变长字符串。当两个字符串在某个较低位已经区分开，MSD 不需要继续检查更低位——可以提前结束。这是下一节的主题。

核心思想一句话总结：LSD 排序把"按字符串整体排序"分解为 $W$ 次"按单个字符排序"，从右到左，每次用稳定的键索引计数排序，利用稳定性的"记忆"效应让低位已确定的相对顺序在高位排序时保持不变，最终实现 $O(WN)$ 线性时间的等长字符串排序。

MSD 字符串排序（最高有效数字优先）详解

1. 核心思想

MSD（Most-Significant-Digit First，最高有效数字优先）字符串排序，是一种从左到右逐位处理字符的排序算法。
它的基本逻辑非常直观：

• 先按第一个字符把所有字符串分成若干组（以 a 开头的一组、以 b 开头的一组……）
• 然后对每一组递归地用同样的方法，按第二个字符再分组
• 不断递归，直到每个子数组只剩一个元素，或者所有字符都比较完毕
  这和快速排序（Quicksort）有些像——都是把大问题分成若干个小的独立子问题，再分别解决。区别在于：

---

对比项	快速排序	MSD 字符串排序
分区数量	2~3 个子数组	R 个子数组（R 为字母表大小）
比较基准	整个键值大小	单个字符

---

2. 字符串末尾的处理约定

字符串长度不同，这是个麻烦。当递归到第 $d$ 位时，有些字符串可能只有 $d-1$ 个字符，已经"到头了"。
解决方案：定义一个辅助函数 charAt(s, d)，当 $d$ 超出字符串长度时返回 $-1$，否则返回该字符的值。
在计数数组 count[] 中，所有返回值统一加 $2$（为什么加 2 而不是加 1？后面会说），这样：

• 返回值 $-1+2=1$：表示字符串在第 $d$ 位已结束（“空字符”）
• 返回值 $c+2$（$c\ge 0$）：表示正常字符
  因此，count[] 数组需要开 $R+2$ 个位置（int count[R+2]），含义如下：

索引 0   : 保留不用（偏移量的副产品）
索引 1   : 在第 d 位就已结束的字符串数量（即较短的串）
索引 2   : 第 d 位字符为第 0 个字母（如 'a'）的字符串数量
索引 3   : 第 d 位字符为第 1 个字母（如 'b'）的字符串数量
...
索引 R+1 : 第 d 位字符为第 R-1 个字母的字符串数量

这样，已经结束的较短字符串（“空字符”）会自动排在所有其他字符串前面，完全符合字典序的要求。

3. 算法流程

整体使用**键索引计数（Key-Indexed Counting）**来完成分区，分四个步骤：

步骤一：统计频率
步骤二：频率转下标（前缀和）
步骤三：按下标分发到辅助数组
步骤四：回写原数组，然后递归各子数组

用一个具体的小例子感受一下。假设待排序数组为：

she  sells  seashells  by  the  sea  shore  the  shells  she  sells  are  surely  seashells

按第一个字符分区后，大致分为：

[are]  [by]  [sea seashells sea shore shells she sells surely seashells]  [the the]
  a组    b组                       s 组                                      t 组

然后对 s 组递归，按第二个字符再分……直到全部有序：

are  by  sea  seashells  seashells  sells  sells  she  she  shells  shore  surely  the  the

4. 递归调用结构示意

5. count[] 数组各阶段含义

下表说明 count[] 在各阶段的含义（以第 $d$ 位字符为例）：

阶段	count[r] 的含义
统计频率后	count[r] = 第 $d$ 位字符值为 $r-2$ 的字符串数量
转为下标后	count[r] = 对应子数组的起始索引
分发完成后	count[r] = 对应子数组的结束索引 + 1

---

6. 完整 C++ 代码（含详细注释）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// ============================================================
// MSD 字符串排序
// ============================================================
// 字母表大小，ASCII 扩展字符集为 256
static const int R = 256;
// 小子数组的阈值：子数组元素个数 <= M 时改用插入排序
// 这是关键优化，能将运行时间降低约 10 倍
static const int M = 15;
// ============================================================
// 辅助函数：取字符串 s 第 d 位的字符值
// 若 d >= s.size()，说明字符串已经到头，返回 -1（表示"空"）
// 调用方会对返回值加 2，使其变为非负整数用于索引
// ============================================================
static int charAt(const std::string& s, int d) {
    if (d < (int)s.size()) {
        return (unsigned char)s[d]; // 强制转 unsigned，避免负数
    }
    return -1; // 字符串在第 d 位已结束
}
// ============================================================
// 专用插入排序：对 a[lo..hi] 排序
// 假设前 d 个字符已知相等，只从第 d 位开始比较
// 避免重复比较已知相等的前缀，效率更高
// ============================================================
static void insertionSort(std::vector<std::string>& a, int lo, int hi, int d) {
    for (int i = lo; i <= hi; i++) {
        // 将 a[i] 插入到 a[lo..i-1] 的正确位置
        for (int j = i; j > lo; j--) {
            // 只比较从第 d 位开始的子串，前 d 位已知相等
            if (a[j].substr(d) < a[j-1].substr(d)) {
                std::swap(a[j], a[j-1]);
            } else {
                break; // 已找到正确位置，提前退出
            }
        }
    }
}
// ============================================================
// MSD 排序核心递归函数
// 对 a[lo..hi] 按第 d 位字符排序（前 d 位已知相等）
// ============================================================
static void msdSort(std::vector<std::string>& a,
                    std::vector<std::string>& aux,
                    int lo, int hi, int d)
{
    // 基本情况 1：子数组足够小，切换为插入排序
    // 这是 MSD 排序中最重要的优化，避免大量微小子数组的开销
    if (hi <= lo + M) {
        insertionSort(a, lo, hi, d);
        return;
    }
    // count[r] 用于频率统计，需要 R+2 个槽位：
    //   索引 0        : 占位，不用
    //   索引 1        : charAt 返回 -1 的字符串（即到达末尾的串）
    //   索引 2..R+1   : charAt 返回 0..R-1 的字符串（正常字符）
    std::vector<int> count(R + 2, 0);
    // ---- 步骤一：统计每个字符值的出现频率 ----
    // charAt(a[i], d) 返回 -1 或 0..R-1
    // 加 2 后变成 1..R+1，存入 count[1..R+1]
    // 这样 count[r+1] 记录字符值为 r-1 的频率
    // 注意：使用 +2 偏移是为了给"到达末尾"的情况（-1）腾出索引 1
    for (int i = lo; i <= hi; i++) {
        count[charAt(a[i], d) + 2]++;
    }
    // ---- 步骤二：频率转换为起始下标（前缀和） ----
    // 执行完毕后，count[r] 就是字符值为 r-1 的子数组的起始位置
    for (int r = 0; r < R + 1; r++) {
        count[r + 1] += count[r];
    }
    // ---- 步骤三：将元素分发到辅助数组 aux ----
    // charAt(a[i], d) + 1 得到该元素应放入的子数组索引
    // count[...] 给出当前可放的位置，放完后该位置后移一格
    for (int i = lo; i <= hi; i++) {
        int bucket = charAt(a[i], d) + 1; // 目标桶编号（0..R）
        aux[lo + count[bucket]++] = a[i]; // 放入辅助数组，并移动指针
    }
    // ---- 步骤四：将辅助数组的内容回写到原数组 ----
    for (int i = lo; i <= hi; i++) {
        a[i] = aux[i];
    }
    // ---- 步骤五：对每个字符值对应的子数组递归排序 ----
    // 注意：r=0 对应"已到末尾"的字符串，它们已经在正确位置，不需要递归
    // 所以从 r=0 开始，但 sort(a, lo+count[0], lo+count[1]-1, d+1) 会因为
    // lo > hi 而直接在插入排序中 return，实际无副作用
    // 为清晰起见，直接从 r=0 循环到 R-1
    for (int r = 0; r < R; r++) {
        // count[r] 是子数组的起始偏移，count[r+1] 是下一个子数组的起始偏移
        // 所以本子数组范围是 [lo + count[r], lo + count[r+1] - 1]
        msdSort(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
    }
}
// ============================================================
// 对外接口：对字符串数组 a 进行 MSD 排序
// ============================================================
void msdStringSort(std::vector<std::string>& a) {
    int n = (int)a.size();
    if (n <= 1) return;
    // 辅助数组，与原数组等长，在递归外层只分配一次，避免重复分配
    std::vector<std::string> aux(n);
    msdSort(a, aux, 0, n - 1, 0);
}
// ============================================================
// 主函数：演示排序效果
// ============================================================
int main() {
    std::vector<std::string> words = {
        "she", "sells", "seashells", "by", "the",
        "sea", "shore", "the", "shells", "she",
        "sells", "are", "surely", "seashells"
    };
    std::cout << "排序前：\n";
    for (const auto& w : words) {
        std::cout << "  " << w << "\n";
    }
    msdStringSort(words);
    std::cout << "\n排序后：\n";
    for (const auto& w : words) {
        std::cout << "  " << w << "\n";
    }
    return 0;
}

7. 运行结果

排序前：
  she  sells  seashells  by  the  sea  shore  the  shells  she  sells  are  surely  seashells
排序后：
  are  by  sea  seashells  seashells  sells  sells  she  she  shells  shore  surely  the  the

8. 三个必须处理的陷阱

8.1 小子数组问题（最关键的优化）

MSD 排序会迅速将大数组分裂成大量微小的子数组。若不加以处理，每个只含 1 个元素的子数组仍然要：

1. 创建 $R+2$ 个槽位的 count[] 数组并清零
2. 遍历一遍统计频率
3. 遍历一遍转前缀和
4. 遍历一遍分发元素
   对于 ASCII（$R=256$），每个长度为 1 的子数组就要白做 $258\times 3$ 次无意义操作。如果有百万个字符串，代价极高。
   解决方案：当子数组长度 $\le M$ 时，改用插入排序。
   实验表明，$M$ 取约 $10\sim 15$ 时，可将运行时间降低至原来的 $1/10$。
   理论上，最优的 $M$ 约为 $\sqrt{R}$：
   $$M_{\text{最优}}\approx \sqrt{R}$$
   推导依据：对 $N$ 个字符串，切到大小为 $M$ 的子数组时：

• 有约 $\frac{N}{M}$ 个子数组，每个调用键索引计数需 $\sim R$ 次操作，共 $\frac{NR}{M}$ 次
• 对这些子数组做插入排序共 $\sim \frac{NM}{4}$ 次比较
  令两者相等：$\frac{NR}{M}=\frac{NM}{4}$，得 $M=2\sqrt{R}$

8.2 大量重复键问题

当很多字符串完全相同时，MSD 会把它们始终分配到同一个子数组，然后每次递归都要处理所有字符。极端情况（全部相同）下，时间复杂度退化为字符总数的线性复杂度，与 LSD 相当，但开销更大。

8.3 额外空间

MSD 排序需要两个辅助结构：

辅助结构	大小	说明
aux[]	$N$	分发用的临时数组，只需分配一次（在最外层），不随递归增加
count[]	$R+2$	必须在每次递归调用中重新分配，因此栈上空间正比于递归深度

---

最坏情况下，递归深度等于最长公共前缀长度 $W$，总空间为：
$$\text{空间}=O(R\cdot W+N)$$
若使用 Unicode（$R=65536$）并有大量长度为 1000 的重复字符串，count[] 占用超过 $65536\times 1000\times 4\text{bytes}\approx 250\text{MB}$，极易耗尽内存。

9. 性能分析

9.1 时间复杂度

设字符串有 $N$ 个，字母表大小为 $R$。
命题 C（随机输入）：平均情况下，MSD 排序约检查 $N{\log }_{R}N$ 个字符。
推导来自递推关系：
$$C_N=R\cdot C_{N/R}+N$$
其中 $N$ 是当前层扫描所有字符串一遍的代价，$R\cdot C_{N/R}$ 是递归处理 $R$ 个大小约为 $N/R$ 的子数组的代价。解此递推式得：
$$C_N\approx N{\log }_{R}N$$

9.2 数组访问次数

命题 D：MSD 排序对 $N$ 个字符串（字母表大小 $R$，平均长度 $w$）需要的数组访问次数在 $8N+3R$（最佳）到 $\sim 7wN+3WR$（最坏，$W$ 为最长字符串长度）之间。

9.3 三种典型场景对比

输入类型           字符检查量
-----------------------------------------
随机字符串          次线性（sublinear）
有大量重复键        接近线性（near-linear）
全部相同（最坏）    线性（linear）

用 ASCII 图示意：

字符串数量 N
|
|  随机：只看前几位就能区分
|  ....
|      ......
|            ........
|                    ............  <- 有重复：需看更多位
|                                ....................................  <- 全相同：看完所有位
+-------------------------------------------------------------------------> 检查的字符数

10. 与指定字母表结合使用

若字符串来自较小的字母表（如只含小写字母，$R=26$），可以通过传入 Alphabet 对象，将字符映射到 $[0,R)$ 范围，大幅减少 count[] 的大小，从而提升性能。需要修改的地方：

1. 构造函数中保存字母表，并读取 $R=\text{alpha.size()}$
2. charAt() 中改为 alpha.toIndex(s[d])

11. 算法整体流程（ASCII 示意）

原始数组: [she, sells, seashells, by, the, sea, shore, the, shells, she, sells, are, surely, seashells]
第0轮 (按第0位字符分区):
  a组: [are]
  b组: [by]
  s组: [she, sells, seashells, sea, shore, shells, she, sells, surely, seashells]
  t组: [the, the]
第1轮 (对s组按第1位字符分区):
  se组: [sells, seashells, sea, sells, seashells]
  sh组: [she, shore, shells, she]
  su组: [surely]
第2轮 (对se组按第2位字符分区):
  sea组: [seashells, sea, seashells]
  sel组: [sells, sells]
第3轮 (对sea组按第3位字符分区):
  sea$组: [sea]        <- $ 表示字符串结束
  seas组: [seashells, seashells]
... 以此类推，直到全部有序
最终结果: [are, by, sea, seashells, seashells, sells, sells, she, she, shells, shore, surely, the, the]

12. 总结对比

---

特性	LSD 字符串排序	MSD 字符串排序
处理方向	从右到左	从左到右
适合场景	定长字符串	变长字符串
平均时间	$O(wN)$	$O(N{\log }_{R}N)$
最坏时间	$O(wN)$	$O(wN)$
额外空间	$O(N+R)$	$O(N+RW)$（$W$ 为最长串）
是否稳定	稳定	稳定
小子数组优化	不需要	必须做，否则慢 10 倍以上

---