如何实现O(n log k)时间复杂度的比较基k-多重集排序算法？

嘿，这个问题抓得很准——针对只有k个不同键的多重集，要做基于比较的排序且时间复杂度压到O(n log k)，确实有几个贴合需求的方案，咱们结合你提到的三路分区快排展开聊：

一、优化版三路分区快速排序 #

你一开始想到三路快排是非常靠谱的方向，普通三路快排是把数组拆成「小于基准、等于基准、大于基准」三部分，而针对k-多重集，我们可以利用“不同键数量少”的特性优化递归逻辑：

• 核心思路：每次选择一个基准元素（建议选当前子数组里的某个不同键），通过三路分区把所有等于基准的元素直接放到最终有序的位置上；然后只递归处理「小于基准」和「大于基准」的两个子数组——这两个子数组的不同键总数最多是k-1（因为基准对应的键已经处理完了）。
• 时间复杂度分析：每次分区操作是O(m)（m是当前子数组的长度），而递归的深度是O(log k)（类似二分，每次不同键的数量至少减半），总时间就是O(n log k)。举个例子，你给的数组{1,1,1,1,2,2,3,4,4,4,5,5}，第一次选2当基准，分区后得到[1,1,1,1]、[2,2]、[3,4,4,4,5,5]；[2,2]已经有序，递归处理左右子数组，左边只有1（不用递归），右边选4当基准，分区后得到[3]、[4,4,4]、[5,5]，再递归处理左右（各自只有一个不同键），整个过程的递归深度只有2层，总操作量远小于普通快排的O(n log n)。
• 注意点：基准选择尽量避开已经处理过的键，比如可以在分区时记录当前子数组的不同键（或者通过比较判断），避免重复选择相同基准浪费时间。

二、基于平衡BST+有序遍历的方案 #

如果不想用快排的递归思路，还可以用平衡二叉搜索树（比如红黑树）来统计+排序：

• 步骤：
  1. 遍历整个数组，把每个元素插入到平衡BST中，同时记录每个键的出现次数——因为BST的插入是基于比较的，且每次插入时间是O(log k)（最多k个不同键），所以这一步总时间是O(n log k)。
  2. 对平衡BST进行中序遍历，得到有序的不同键列表（中序遍历平衡BST的结果是升序的），这一步时间是O(k)。
  3. 最后根据每个键的出现次数，把重复元素依次填充到结果数组中，这一步是O(n)。
• 时间复杂度：O(n log k + k + n) = O(n log k)，完全符合要求。

三、锦标赛排序（堆优化版） #

另一个思路是先提取所有不同键，再排序后展开：

• 步骤：
  1. 遍历数组，维护一个大小不超过k的有序列表（用二分查找判断元素是否已存在，不存在则插入到正确位置），这一步每个元素的操作是O(log k)，总时间O(n log k)。
  2. 对这k个不同键用基于比较的排序（比如堆排序、快速排序），时间是O(k log k)。
  3. 遍历排序后的键列表，按出现次数重复填充到结果数组，时间O(n)。
• 时间复杂度：O(n log k + k log k + n) = O(n log k)，因为k ≤ n，所以k log k不会超过n log k。

总结一下，你一开始想到的三路分区快排优化是最贴近常规排序思路的方案，实现起来也比较直观；如果需要稳定排序的话，平衡BST的方案会更合适。

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