这问题抓得很准啊！当要排序的n个整数范围是[1, n^{α]时，计数排序确实因为空间需求直接拉满（要开n}α大小的数组，这谁顶得住）而没法用。这时候**基数排序（Radix Sort）**就是专门为这种场景设计的方案，能完美利用数值范围是n的幂次这个特性。

核心逻辑 #

把每个数拆成以n为基数的数位——这样每个数位的取值范围就被压缩到了[0, n-1]，刚好能用上计数排序处理每一位，而且空间完全可控。

具体操作步骤 #

• 先确定数位长度：因为最大值是n^{α，用n进制表示的话，最多也就α+1位（比如n=10，α=2时，n}α=100，10进制是3位），这个数位数量是固定的常数（因为α是给定的正整数）。
• 从最低位到最高位，依次对每个数位做计数排序：
  1. 提取当前要处理的数位（比如对x来说，第k位的数值是(x // n^(k-1)) % n）。
  2. 用计数排序对原数组按当前数位的值排序，排序后保持之前数位的有序性（这就是基数排序的稳定性优势）。
• 等所有数位都处理完，整个数组就完全有序了。

时间&空间复杂度分析 #

• 时间复杂度：每一轮计数排序的时间是O(n)（遍历数组+处理计数数组），总共要处理O(α)轮，所以总时间是O(α*n)。因为α是固定的正整数，这等价于线性时间O(n)，比O(n log n)的比较类排序高效得多。
• 空间复杂度：每轮只需要O(n)的额外空间（计数数组大小n，加上临时存储排序结果的数组大小n），对比直接计数排序需要的O(n^α)空间，简直是天差地别。

关键优势 #

为什么选n作为基数？就是为了把每个数位的范围锁死在[0, n-1]，完美适配计数排序的能力，既避开了大范围的问题，又保留了计数排序的线性时间优势。

要是你还有具体实现上的疑问——比如怎么高效提取数位，或者针对不同α值的小优化——随时唠！

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