具有大部分重复元素的数组的快速排序算法? [英] Fast sort algorithms for arrays with mostly duplicated elements?

问题描述

有哪些有效的方法可以对大多数包含少量重复元素的数组进行排序?也就是说，列表如下:

What are efficient ways to sort arrays that have mostly a small set of duplicated elements? That is, a list like:

{10，10，55，10，999，8851243，10，55，55，55，10，999，8851243，10}

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

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

Assuming that the order of equal elements doesn't matter, what are good worst-case/average-case algorithms?

推荐答案

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

In practice, you can first iterate through the array once and use a hash table the count the number of occurrences of the individual elements (this is O(n) where n = size of the list). Then take all the unique elements and sort them (this is O(k log k) where k = number of unique elements), and then expand this back to a list of n elements in O(n) steps, recovering the counts from the hash table. If k << n you save time.

这篇关于具有大部分重复元素的数组的快速排序算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！