基数排序(Radix Sort)桶大小不符单元测试要求的问题求助

核心排查方向 #

先明确问题本质：最终排序结果正确，但单元测试中桶0的统计大小与预期不符，说明排序的最终结果逻辑没问题，但桶的计数/映射逻辑和测试用例的预期不匹配，重点排查以下几点：

1. 检查余数到桶索引的映射逻辑（最常见错误） #

降序基数排序的核心是反转余数的桶映射：升序时余数r对应桶r，但降序时余数r应对应桶base-1 - r（比如base=7时，余数0对应桶6，余数6对应桶0）。如果你的代码直接沿用了升序的映射逻辑，桶0的统计值就会和测试预期的桶6值一致，导致报错。

错误示例（升序映射套用降序）：

// 错误：降序时未反转余数
int remainder = num % base;
count[remainder]++;

正确的降序映射：

int remainder = num % base;
// 反转余数，将大余数映射到前序桶，小余数映射到后序桶
int bucketIdx = base - 1 - remainder;
count[bucketIdx]++;

2. 验证单元测试的预期合理性 #

确认测试用例的预期值是基于降序排序的桶分布，而非升序。比如测试用例数组[0,3,1,6]（base=7）：

• 升序第一轮桶0大小是1（仅数字0）
• 降序第一轮桶0大小是1（仅数字6，因为余数6被映射到桶0）
  如果测试预期是升序的桶0大小，那你的代码逻辑没问题，是测试用例的预期错了。

3. 边界值的余数处理 #

• 数字0：0对base取余始终为0，降序下应映射到最后一个桶（base-1），如果错误放到桶0，会导致桶0大小超出预期。
• 负数：不同语言中负数取余的结果不同（比如Java中-1%7=-1，Python中-1%7=6），如果数组包含负数，需先统一将所有数转为正数（加偏移量），处理完再还原，否则余数计算错误会导致桶计数混乱。
• 位数不足的数：处理高位时，位数不足的数余数为0，降序下应映射到最后一个桶，而非桶0。

4. 手动复现定位问题 #

拿一个极小的测试用例手动计算桶分布，和代码输出对比：
比如数组[5,0,2,6]，base=7，降序排序第一轮（个位）：

• 各数余数：5,0,2,6
• 降序映射后的桶索引：1（7-1-5）、6（7-1-0）、4（7-1-2）、0（7-1-6）
• 桶0的大小应为1（仅数字6）

如果代码输出的桶0大小不是1，直接定位到余数映射的代码段修改即可。

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