题目重点：不用内置排序，按 (出现次数升序, 数值降序) 排列数组；用频次表加自写归并排序实现并分析稳定性。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入是整数列表；输出包含原数组每个元素及其重复次数，只改顺序。
- 不能调用 built-in sort/sorted；允许使用哈希计数和手写归并排序。
- 同一数值元素完全等价，无需区分它们原来的身份。
解题路线
- 先一遍 Counter 计算每个整数的全局出现次数。比较器先比 freq[a] 与 freq[b]，较小者在前；频次相同则数值较大的在前。
- 用递归归并排序：左右半区各排序，再按比较器归并。相等时优先取左侧，保持稳定性，虽然同值元素不可区分。
- 对每个输入位置排序，结果自然保留重复项；如果先排序 distinct keys，也可以再按频次展开，但必须明确展开发生在排序之后。
- 手写排序的重点是比较器满足全序；不应偷偷调用语言内置排序绕过面试官约束。
手动走一遍
[2,3,1,3,2] 中 1 出现 1 次、2 和 3 各出现 2 次。1 在前；同频 3 大于 2，故输出 [1,3,3,2,2]。负数比较仍按整数大小，-1 大于 -2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
from collections.abc import Sequence
def frequency_sort(values: Sequence[int]) -> list[int]:
"""Frequency ascending, value descending on ties; no built-in sort."""
freq = Counter(values)
items = list(values)
def before(a: int, b: int) -> bool:
return (freq[a], -a) <= (freq[b], -b)
def merge_sort(part: list[int]) -> list[int]:
if len(part) <= 1:
return part
mid = len(part) // 2
left, right = merge_sort(part[:mid]), merge_sort(part[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if before(left[i], right[j]):
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return result
return merge_sort(items)
if __name__ == "__main__":
assert frequency_sort([2, 3, 1, 3, 2]) == [1, 3, 3, 2, 2]
复杂度
计数 O(n) 预期时间、O(d) 空间，归并 O(n log n) 时间、O(n) 辅助空间，加递归栈 O(log n)，d 为不同值数。代码切片会复制子数组，但总额外峰值仍为 O(n) 量级。
易错点与追问
容易失分的边界
- 把同频数值按升序排。
- 只输出不同整数，丢掉重复项。
- 用 Counter.most_common 或 sorted 违反‘自己写 sort’约束。
- 归并比较器前后分支不一致，导致排序非传递。
- 将 SQL merge 的未知表结构补成具体题目；题目未明确。
继续深挖
- 若数据量大但数值范围小，计数桶如何减少比较排序成本？
- 数据放不进内存时，如何先聚合频次再外部排序？
- 如果要稳定保留同键对象的原位置，需要在排序项中保存什么？
