如何在线性时间内排序n个长度为k的小写英文单词？求指导

嘿，你遇到的这个问题正好是**基数排序（Radix Sort）**的典型应用场景！它完美解决了你只用单次计数排序只能排首字符的问题，而且全程保持线性时间复杂度，完全符合你的需求。

核心思路 #

基数排序的本质是针对多关键字（这里就是单词的每个字符），依次使用稳定排序算法（比如你已经掌握的计数排序）进行排序。因为计数排序是稳定的——也就是当两个元素的当前排序关键字相同时，它们的相对位置会和排序前保持一致——所以每一轮排序只会修正当前字符位置的顺序，不会破坏之前已经排好的更高优先级的顺序。

对于长度固定为k的单词，我们可以选择**从右到左（最低有效位到最高有效位）**依次对每个字符位置进行排序：

• 先按第k位（最后一个字符）排序，此时所有单词的最后一位是有序的，且前面字符相同的单词相对位置不变
• 再用这个结果按第k-1位排序，此时第k-1位有序，且第k位的顺序被保留
• 重复这个过程，直到对第1位（首字符）完成排序，最终得到的就是完全符合字典序的单词列表

当然，如果习惯从左到右排序也可以，但需要对每个首字符相同的分组单独处理后续字符，效率不如从右到左的全局稳定排序高。

具体步骤（结合计数排序） #

因为单词仅包含a-z，每个字符可以映射为0-25的整数（a→0，b→1，…，z→25），计数排序的数组大小固定为26，非常高效。这里以稳定计数排序为例：

1. 实现稳定版计数排序

针对单个字符位置的排序，稳定计数排序的关键步骤：

• 统计当前字符位置上，每个字符（0-25）出现的次数，得到count数组
• 计算前缀和数组prefix，prefix[c]表示小于等于c的字符的总个数，用来确定每个元素在输出数组中的起始位置
• 从后往前遍历输入数组（这是保证稳定的核心！从前往后会打乱之前的相对顺序），将每个单词放到输出数组的对应位置，然后count[c]减1

2. 循环处理每个字符位置

从第k位开始，到第1位结束，每一轮都用上面的稳定计数排序对当前字符位置进行排序，将排序后的结果作为下一轮的输入。

举个简单例子 #

假设我们有5个长度为4的单词：["baca", "apple", "apce", "blue", "bery"]

1. 先按第4位排序：
   字符分别是a(0), e(4), e(4), e(4), y(24)
   稳定排序后得到：["baca", "apple", "apce", "blue", "bery"]（前四个的第4位a/e/e/e，保持原相对位置）
2. 再按第3位排序：
   字符分别是c(2), p(15), c(2), u(20), r(17)
   稳定排序后得到：["baca", "apce", "apple", "bery", "blue"]（第3位c/c/p/r/u，且第4位的顺序被保留）
3. 接着按第2位排序，最后按第1位排序，最终就能得到完全有序的列表。

时间复杂度分析 #

每个字符位置的计数排序时间是O(n + 26)，总共k轮，所以总时间是O(k*(n+26))。因为k是固定的单词长度，所以整体是线性时间O(n)，完全满足你的性能需求。

内容的提问来源于stack exchange，提问作者Dan