key-indexed counting的机制Q那么我还有一个疑惑你看这句for (int i 0; i N; i)count[a[i]1];这是第19页的代码。a[i]1这个能做index说明这里是一个数字。可是a里面是一堆字符。这样怎么做数字还是说我们是额外再建立一个数组然后这个新数组和字符数组一一对应用数字来取代字符A不需要额外建数组。char本身就是整数。Java 的char类型在内存里就是一个 16 位无符号整数。a就是 97b就是 98c就是 99依此类推。屏幕上显示的是字形但内存里存的是整数值。所以a[i] 1的物理动作是从a[i]取出一个char它的值是一个整数比如d是 100。把这个整数加 1得到 101。用 101 作为索引去访问count数组。count[a[i]1]等价于javaint code a[i]; // d → 100 int index code 1; // 101 count[index]; // count[101]这就是 PPT 第 18 页说的“键是整数可以直接作为数组索引”。字符就是整数不需要任何转换表。ASCII 表本身就是这个映射但它已经内置在char的编码里了。用你的图追踪一次数组a的内容字符和它们的整数值a[0] d 100a[1] a 97a[2] c 99a[3] f 102a[4] f 102a[5] b 98...执行count[a[i]1]i0count[1001]→count[101]i1count[971]→count[98]i2count[991]→count[100]i3count[1021]→count[103]因为a97b98c99d100e101f102所以count[98]统计的是a的出现次数count[99]统计bcount[100]统计ccount[101]统计dcount[102]统计ecount[103]统计f。1的作用是让count[r1]记录字符编码为 r 的频率这样后续累积时count[r]可以直接作为该字符的起始位置。Q你的意思是说count不是R个的大小或许我应该这么说我之前的理解是例如我们现在有abcdefR就是这里一共的个数也就是6然后a是1b是2以此类推count的大小是R17原来不是假使我们这里使用了一个有256种字符的编码那么count实际应该是大小257A你的疑惑在于“R 到底指什么”。R 不是“当前实际出现的字符种类数”而是字母表大小alphabet size也就是键的可能取值范围。PPT 在第 14 页定义了 RR是字母表中数字的个数。如果是 DNAR4A, C, T, G。如果是扩展 ASCIIR256。你的两种场景分别对应什么场景 A你手动映射 a1, b2, ..., f6如果你在代码里预先做了一个映射把a变成 1b变成 2那么 R 就是 6count数组大小 R1 7。但这样做需要额外的映射步骤比如查表或减法代码会变成count[map(a[i])1]。场景 B直接用字符的编码PPT 采用的方式Java 的char直接就是 ASCII/Unicode 编码。a的编码是 97f的编码是 102。如果直接用这个编码去访问数组count[a[i]1]就会去访问count[98]、count[103]等索引。为了保证数组不越界count数组的长度必须覆盖最大的可能编码。如果字符集是扩展 ASCII最大的字符编码是 255。所以R 256count数组大小 R1 257。此时count[0]到count[96]都是空槽位值为 0因为a的编码是 97所以数据是从count[98]开始填充的。这会浪费前面 97 个格子但初始化的代价是 O(R) O(256)是常数时间不影响 O(NR) 的整体复杂度。为什么不用手动映射因为在字符串排序如 LSD、MSD中字符串很长每次比较都去查映射表太慢了。直接用字符的编码作为数组索引省去了映射开销只需要在初始化时付出 O(R) 的代价。回答你的原话“假使我们这里使用了一个有256种字符的编码那么count实际应该是大小257”是的。如果 R256count数组的长度就是 257索引 0 到 256。count[0]是哨兵位后续计算累积时用到count[1]到count[256]用来存储字符编码 0 到 255 的频率。这就是为什么 MSD 代码里写int[] count new int[R2];的原因——R1 个格子用来存原始编码0 到 R-1 映射到 1 到 R再加 1 个格子索引 0作为哨兵。总共 R2 个格子。MSD radix sortQ我好像终于看懂了这里看上一页charAt是在[String,d]的String中取第i个char这里的a是String类型的array每个元素是一个String。我们创建的count具有R2个格子但你可以发现index1的格子留给了我们虚拟出来的-1所以这里的机制跟之前是一样的A完全正确。你刚刚说的这段话就是第 40 页 MSD 实现中最核心的映射关系。把它精炼成物理事实a是String[]a[i]取出一个 String 对象charAt(a[i], d)在这个 String 上取第d个字符。count数组长度是R2count[0]哨兵位用于计算累积时提供起始 0。count[1]专门留给charAt返回-1的情况虚拟结束符。count[2]到count[R1]留给真实的字符编码0到R-1。映射机制charAt(...) 2把-1映射到1把0映射到2。这和之前 key-indexed counting 的1偏移是同一个机制只是多偏移了一位来容纳那个虚拟出来的-1。累积与递归边界做完前缀和之后count[r]表示“所有小于第 r 个字符的元素个数”。所以第 r 个字符对应的子数组在排序后位于lo count[r]到lo count[r1] - 1。下一层递归sort(..., d1)就按这个边界切分。你说“跟之前是一样的”这个判断非常精准。MSD 本质上就是“先按首字符做一次 key-indexed counting然后对每一个字符桶内部递归地再做 key-indexed counting”。Q我好奇第40页为什么我们不能重复使用count我看做完这一轮count也没用了因为count中有用的信息已经在递归调用中被取出来过了呀A你的观察是每一轮结束后count里的累积信息已经被用来决定递归调用的子数组边界了所以似乎可以重用。不能重用的物理原因递归是嵌套的每一层在它的循环中需要跨多个递归调用保持count有效。看第 40 页的代码javaint[] count new int[R2]; // ... 填充 count做累积 ... for (int r 0; r R; r) sort(a, aux, lo count[r], lo count[r1] - 1, d1);这个循环会执行 R 次。每次迭代都需要读取count[r]和count[r1]来确定子数组的边界。如果所有递归层级共用一个count数组那么第一次递归调用r0进入更深层级后会更写这个共享数组。当它返回时当前层的count[1]和count[2]已经被覆盖r1的边界就错了。用一个最小例子看假设字符串数组是[ant, bat, cat]R256d0。第 0 层统计后count[a1] 1count[b1] 1count[c1] 1。累积后count[a] 0count[b] 1count[c] 2。排序后[ant, bat, cat]。现在进入循环r a调用sort(a, aux, lo0, lo1-1, 1)。这个递归调用处理[ant]它会创建自己的count数组如果每次新建或者覆盖共享的count如果共享。递归返回后r变成b。r b需要读取count[b] 1和count[c] 2。如果count被上一轮递归覆盖了这两个值就丢了。因此每一层递归必须拥有自己的count数组或者在进入递归前把count复制一份保存起来。复制一份的开销和新建一个数组一样所以代码选择了在每一层新建。空间代价每一层递归新建一个大小为R2的count数组。递归深度为 D最长公共前缀长度所以count数组的总空间是 O(D·R)。这就是第 44 页表格里 MSD 额外空间写N D·R的原因。如果count可以重用空间会降到 O(NR)。但物理上做不到因为递归的嵌套结构要求每一层保留自己的count直到它的循环结束。啊我明白了因为这里是一个循环。在同一个count下不止调用一轮。Q虽然画着很混乱但大概的意思是它的指针是这样走在a组下一直进入小组然后回到次小组再进小组。有点类似于quicksort而不是mergesort因为mergesort越合并规模越大。AMSD 基数排序的递归路径是前序pre-order确实和快速排序一样而不是归并排序。物理动作对比归并排序后序先递归左半。再递归右半。最后合并在返回的路上做事。MSD 基数排序 / 快速排序前序先按当前字符/基准分区在进入的路上做事。再递归处理第一个子数组一直到最深处。返回上一层处理下一个子数组。再返回再处理下一个。你描述的“在 a 组下一直进入小组然后回到次小组再进小组”正是这个前序递归的物理过程。以第 38 页的图为例字符串数组按首字符分成 a、b、s、t 四组。递归路径是处理 a 组只有 are。进入sort(a组, d1)。深度 1。如果 a 组只有 1 个字符串直接返回。回到根处理 b 组只有 by。进入sort(b组, d1)。深度 1。返回。回到根处理 s 组很多字符串。进入sort(s组, d1)。在 s 组内按第二个字符分成 se、sh、su 三组。先处理 se 组。进入sort(se组, d2)。再处理 sh 组。进入sort(sh组, d2)。再处理 su 组。进入sort(su组, d2)。回到根处理 t 组。在 s 组内的递归用的是 s 组这个子数组的lo和hi。当它处理 se 组时是在 s 组的范围内再切出一个更小的范围。处理完 se回到 s 组的循环处理 sh。为什么像快速排序不像归并排序归并排序是自底向上先分成 1 个元素再两两合并规模从 1 变 2 变 4 变 N。处理顺序是“先做完左边全部再做右边全部最后合并”。合并动作在返回途中。MSD 基数排序是自顶向下先按首字符分成 R 组再对每组按第二字符分成 R 组规模从 N 变成 N/R 再变成 N/R²。处理顺序是“先进入第一个子组把它彻底排完再回到上一层处理第二个子组”。分区动作在进入途中。这个前序递归结构和你之前手推快速排序时追踪的sort(lo, j-1)和sort(j1, hi)是完全一样的。区别只在于快速排序用基准值把数组分成“小于”和“大于”两组MSD 用当前字符把数组分成 R 组。为什么图看起来混乱因为图中同时画了每一层的数组状态和递归调用箭头。箭头交叉是因为每一层递归都在同一个数组的不同子区间上操作lo和hi在不断变化。深度越深子区间越小但画在平面上看起来是重叠的。箭头从父区间指向子区间子区间再指向更小的子区间形成树状的嵌套。如果你在纸上画一个树形结构根是[0, N-1]子节点是分割后的各子区间就会清楚很多。图中的线只是把这个树结构画在了数组的上下方。性能问题Q每个函数调用需要自己的 count[] 数组。ASCII256 个计数对于 N2比复制过程慢 100 倍。Unicode65,536 个计数对于 N2慢 32,000 倍。“Huge number of small subarrays because of recursion.”物理含义递归到深度 d 时如果子数组很小比如只有 2 个字符串仍然要分配和初始化一个大小为 R2 的 count 数组。R256 时初始化这个数组的开销远大于直接比较这两个字符串的开销。递归会产生大量小的子数组每个都要执行完整的键索引计数流程导致大量无效开销。这句对于N2慢32000倍没看懂。莫名其妙跳出来个NN是什么呢一个字符串内的字符数那么这里在比较复制所有字符串和对字符串进行key-indexed countingcounting也有对字符串的复制但是由于其他操作会比单纯复制慢出100倍AN 是什么在 MSD 基数排序中N 是当前正在排序的子数组里的字符串个数不是字符串的长度。当你对整个数组排序时N 是数组的总长度比如 100 万个字符串。当你递归到某个子数组时N 就是这个子数组里剩余的字符串个数。如果某个子数组只剩下 2 个字符串那么这一层的 N 2。比较的是哪两件事第 41 页在比较用键索引计数处理长度 N2 的String子数组需要多少操作和单纯复制这 2 个元素相比慢多少倍。单纯复制 2 个元素copy pass的物理动作把 2 个字符串从辅助数组复制回原数组。读 2 次写 2 次。操作数 ≈ 2。用键索引计数处理 N2 的子数组的物理动作分配count[R2]数组。初始化count数组全部清零R2 次写。遍历count做前缀和R 次读 R 次写。遍历 2 个元素读a[i]读写count写aux约 8 次。把 2 个元素从aux复制回a约 4 次。主要开销是第 2、3 步它们的代价与 N 无关只与 R 有关。当 R 65,536 时第 2、3 步大约是 65,536 × 3 ≈ 196,608 次数组访问。而复制 2 个元素只要 2 次。比值大约是 100,000 倍。PPT 说的 32,000 倍是一个保守的估计但数量级一致。为什么会“莫名其妙”出现这个对比因为 MSD 是递归切分的。每一次递归调用sort(a, aux, lo, hi, d)都会新建一个count数组然后做一次键索引计数。如果某个子数组只有 2 个字符串N2它依然要执行完整的键索引计数流程包括新建和初始化一个大小为 R2 的count数组。这份开销与 N 无关与 R 成正比。递归会产生大量这样的小子数组递归树的叶子附近全是小数组。每个小数组都要花 O(R) 的时间去初始化count而它们本身只有几个元素。这就是“huge number of small subarrays”的物理含义。修正你的理解“counting 也有对字符串的复制但是由于其他操作会比单纯复制慢出 100 倍”对。键索引计数确实也做了和复制相同的动作把元素从aux搬回a但它额外做了大量与 R 有关的操作初始化count、计算前缀和。当 N 很小、R 很大时这些与 R 有关的操作占据了绝对主导导致它比单纯复制慢了几万倍。所以解决方案是当子数组小到一定程度比如 N 10不要再走键索引计数直接改用插入排序。这样就把那些与 R 有关的浪费全部砍掉了。Q我明白了这里是在告诉R256或别的所以count数组每次都会分配这个大小为了不用每次都去手工映射但这个时候已经违背想要快的初衷了A完全正确。它的初衷是“用空间换时间”为了省去每次比较字符时“查表映射”或“减法计算”的时间开销直接把char作为整数当成数组索引。代价是count数组的大小必须覆盖整个字母表范围R2。这在 N 很大时O(R)O(R) 的开销被 O(N)的巨大收益掩盖了。但在递归切分的末期N 变小了比如只剩 2 个字符串。R 没变依然要分配R2大小的count数组并扫描初始化。此时 N≪R原本被掩盖的 O(R) 成本占据绝对主导直接摧毁了 MSD 的性能连单纯的复制都比不上。这确实违背了“想要快”的初衷。而下一页第 42 页就是针对这个矛盾给出的解决方案Cutoff to insertion sort。物理动作很直接当子数组的 N 小于某个阈值比如 10时直接抛弃 MSD 流程改用插入排序。因为插入排序在小数组上是 O(N2)当 N2 时只需 1 次比较就能排好完全避开了那个 O(R)的初始化陷阱。解决方案