4字符英文单词字典序降序排序的基数排序解法正确性咨询

解法正确性判断 #

你的思路整体正确，该场景下基数排序确实是最优选择，不过有几个实现细节需要调整才能得到正确结果。

详细说明 #

• 复杂度合理性：单词长度固定为4，可选基数大小为26，因此整体时间复杂度为O(4*(n+26))，确实属于线性时间复杂度，优于基于比较的排序算法的O(nlogn)理论下限。
• 字典序适配注意事项：
  1. 要使用*最高位优先（MSD）的基数排序顺序，从单词的第一个字母（最左位）开始迭代排序，不能使用最低位优先（LSD）*的逻辑，否则排序结果不符合字典序优先级规则。
  2. 内层调用的计数排序需要适配降序规则：可以调整计数排序的累加顺序实现降序，也可以将字母映射为索引时把A映射为25、Z映射为0，用升序计数排序间接得到降序结果。
• 伪代码的补充修正：你给出的伪代码缺少结果回写的逻辑，每轮计数排序完成后需要把输出数组的结果回写到原数组，作为下一轮排序的输入，修正后的参考伪代码如下：

radixsort(array a, int d)
    for int i = 1 to d // i对应从左数第i位，按最高位到最低位顺序迭代
        a = countingsort(a, i, 26, is_desc=True)

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