时间复杂度层面计数排序与基数排序哪种更适合O(n)排序需求？

针对元素取自集合{0,1,…,n}、需要O(n)时间复杂度排序的场景，两者的选择建议如下：

优先选择计数排序的情况 #

• 当前场景下优先选计数排序：你的元素取值范围刚好和数组长度量级匹配，只需要额外开辟一个大小为n+1的计数数组，空间复杂度为O(n)，时间复杂度稳定为O(n)。
• 计数排序实现逻辑更简单，仅需要2轮遍历：第一轮统计每个元素的出现次数，第二轮按计数顺序回填排序结果，运行的常数时间开销远低于基数排序。
• 不需要后续扩展排序能力，仅针对当前固定范围的整数排序的场景，计数排序是最优解。

考虑使用基数排序的情况 #

• 后续需要扩展支持更大取值范围的整数排序：比如后续要处理的元素最大值远大于数组长度（比如最大值到10^9而数组长度仍为n），此时计数排序需要开辟的计数数组空间会大到不可接受，基数排序仅需要按整数位数逐轮排序，依然能保持近似线性的时间复杂度。
• 需要利用排序的稳定性处理多规则排序场景：比如需要先按高位优先级排序、再按低位优先级排序的复合排序规则，基数排序的稳定排序特性更适合做扩展。

针对你当前的明确需求，直接选择计数排序即可，无论是开发成本还是运行效率都优于基数排序，完全能满足O(n)时间复杂度的要求。

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