满足特定出现次数的数组Θ(n)时间排序算法设计与分析

核心思路 #

利用题目中元素出现次数的层级特性（次数为 $n/2, n/4, ..., 1$，其中 $n=2^k$），结合摩尔投票法快速定位当前数组中出现次数最多的元素，再递归处理剩余元素，最后合并有序结果。全程仅使用数组、栈（或递归栈）等基础结构，无需字典/哈希表。

算法步骤 #

1. 基础情况处理 #

若当前数组长度为1，直接返回该数组（天然有序）。

2. 摩尔投票法找高频元素 #

遍历数组，找出出现次数为 $n/2$ 的元素（$n$ 为当前对应的 $2^k$，数组长度为 $n-1$）：

• 初始化候选元素 candidate 为数组首元素，计数 count = 1
• 遍历剩余元素：
  • 若当前元素等于 candidate，count++
  • 否则 count--；若 count 变为0，更新 candidate 为当前元素，重置 count=1
• 遍历结束后，candidate 即为出现次数最多的元素（因其数量超过其他所有元素总和，必然能被选出）

3. 元素分离 #

遍历数组，将所有等于 candidate 的元素收集为一个子数组，剩余元素收集为 rest 数组。

4. 递归/栈处理剩余元素 #

对 rest 数组重复上述步骤：rest 的长度为 $n/2 -1$，对应 $n'=2^{k-1}$，完全符合题目中的次数分布规则。
若不想用递归，可使用栈存储待处理的数组片段：

• 初始化栈，将原数组压入栈
• 弹出栈顶数组，按上述步骤处理，将 candidate 子数组和处理后的 rest 有序数组压入栈
• 当栈中所有片段都处理为有序数组后，依次合并所有有序片段

5. 合并有序结果 #

由于递归处理后的 rest 是有序数组，candidate 的子数组是相同元素，只需比较两者的大小关系，将 candidate 子数组插入到 rest 有序数组的合适位置，得到最终有序数组。

示例演示 #

输入：[5,1,2,1,2,2,2]（$n=8=2^3$，对应次数4、2、1）

1. 摩尔投票选出出现4次的 2，收集为 [2,2,2,2]，剩余数组 [5,1,1]
2. 处理 [5,1,1]（$n'=4=2^2$，次数2、1），摩尔投票选出 1，收集为 [1,1]，剩余数组 [5]
3. 处理 [5]，直接返回 [5]
4. 合并：[1,1] 与 [5] 合并为 [1,1,5]，再与 [2,2,2,2] 合并为 [1,1,2,2,2,2,5]，与示例输出一致

时间复杂度分析 #

• 每次处理数组的时间为 Θ(m)（m为当前数组长度）
• 总时间递推式为：$T(n-1) = T(n/2 -1) + Θ(n-1)$
• 展开求和：$Θ(n) + Θ(n/2) + Θ(n/4) + ... + Θ(1)$，这是一个等比数列，总和为 Θ(n)（因为总和小于2n）
• 最坏情况下，每次都需完整扫描数组，总时间仍为 Θ(n)，满足要求

关键验证 #

• 摩尔投票法的正确性：高频元素数量为 $n/2$，其他元素总和为 $n/2 -1$，高频元素数量超过其他元素总和，因此摩尔投票法必然能正确选出它
• 无字典/哈希表：全程仅使用数组、栈（或递归栈），符合题目限制

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