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

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你节省时间.

Answer 2

我会尝试使用一些映射函数进行计数排序。IE。您不会使用大小等于元素范围的频率数组，而是会遍历数组，记下不同的元素并在映射函数中使用它们到频率数组。

这样算法只有一个额外的迭代和一个映射函数，它应该在一个恒定的时间内工作（使用某种哈希表）。这种方法的复杂性是O(n)，这应该是最佳的。