能否用基数排序（含数位计数排序）在Θ(n)时间内排序n个不同数字？

你的结论不完全正确，具体要取决于待排序数字的位数限制：

• 基数排序的总时间复杂度公式为 Θ(d*(n+k))，其中：
  • d 是待排序数字的最大位数
  • n 是元素总数
  • k 是基数（比如十进制排序时k=10）
• 你推导中假设d是固定值，这个前提只有在所有数字的位数有明确上界时成立（比如排序32位整数，d=32是常数），此时总时间复杂度确实是Θ(n)，因为常数因子会被大O符号忽略。
• 如果数字的位数d和n相关（比如要排序的n个不同数字里，最大数的位数是Θ(log n)，甚至极端情况存在位数为Θ(n)的数字），那总时间复杂度会变成Θ(n log n)甚至更差，无法达到线性时间。
• 补充：作为基数排序子过程的计数排序，每个数位处理的时间是Θ(n+k)，当k为常数时这一步是线性的，但核心变量还是d的取值。

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