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

EN

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

我会尝试使用一些映射函数的Counting sort。即。您不会使用大小等于元素范围的频率数组，而是迭代数组，写下不同的元素，并在频率数组的映射函数中使用它们。

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

不是最好的算法，但很简单：

你可以把所有的东西都放在trie里，然后把树叶放在柜台上。这应该是O(n*m)，其中n是元素的数量，m是最大元素的大小(通常是一个常量，但不是必须的)。然后预排序遍历tie，当你点击一个叶子时输出当前键的counter元素。这应该只需要O(n+p)，其中p是trie的大小，与n相比应该很小。