performance - 具有最多重复元素的数组的快速排序算法？

Question

有什么有效的方法可以对主要包含一小组重复元素的数组进行排序？也就是说，列表如下:

{ 10, 10, 55, 10, 999, 8851243, 10, 55, 55, 55, 10, 999, 8851243, 10 }

假设 equal 元素的顺序无关紧要，什么是好的最坏情况/平均情况算法？

Answer 1

实际上，您可以先遍历数组一次，然后使用哈希表计算单个元素出现的次数(这是 O(n)，其中 n = 列表的大小)。然后获取所有唯一元素并对它们进行排序(这是 O(k log k)，其中 k = 唯一元素的数量)，然后在 O(n) 步中将其扩展回 n 个元素的列表，从中恢复计数哈希表。如果 k << n 你节省时间。