含重复元素（已知出现频率）的数组能否线性时间排序的证明

首先明确两个核心前提：

• 所有比较类排序算法的时间复杂度下界为Ω(n log n)，这是基于决策树模型的严格结论，无法突破。
• 计数排序（count-sort）、基数排序（radix-sort）这类非比较类线性排序算法，其时间复杂度依赖于元素的取值范围（计数排序为O(n + k)，k是元素取值区间大小；基数排序为O(n*d)，d是元素的位数），而非元素的重复次数。

针对题目中两种场景（无论α是常数还是与n同阶），我们都可以构造反例证明不存在通用的线性时间排序算法，具体推导如下：

反例构造逻辑 #

无论α的取值如何（只要α < n），我们可以构造这样的数组：

• 包含α个重复元素x；
• 剩余n-α个元素为互不相同、且取值范围极大的整数（例如每个元素都是唯一的、大小在[1, 2^n]区间内的整数）。

针对比较类排序的分析 #

比较类排序仅通过元素间的大小比较完成排序，对于数组中n-α个互不相同的元素，排序它们的时间复杂度下界为Ω((n-α) log(n-α))：

• 若α是常数（α=O(1)），则n-α=Θ(n)，下界为Ω(n log n)，远超线性时间；
• 若α=Ω(n)（即n-α=Θ(n)），下界同样为Ω(n log n)，无法达到线性时间。

针对非比较类线性排序的分析 #

• 计数排序：需要的时间为O(n + k)，其中k是元素的最大取值与最小取值的差+1。此处k=2^{n，时间复杂度变为O(2}n)，远大于线性时间O(n)；
• 基数排序：时间复杂度为O(n*d)，其中d是元素的二进制位数。此处d=n，时间复杂度变为O(n²)，同样不是线性时间。

核心结论 #

仅知道数组中某个元素x出现α次，并不能限制其他元素的取值范围和多样性。只要构造出包含Ω(n)个取值范围极大的唯一元素的数组，无论是比较类排序还是非比较类排序，都无法实现线性时间排序。

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