algorithm - 排序时 "few-unique"的含义是什么？

Question

全部。

http://www.sorting-algorithms.com/quick-sort-3-way

在上述站点的快速排序3路划分算法中，我发现了4种不同的情况。 我理解随机的、几乎排序的、相反的情况。 但什么是“少数独特”？？？这意味着大整数 key ？ 您能详细说明一下吗？ 谢谢。

Answer 1

在这种情况下，我认为没有什么独特的方法:即使你有一个巨大的数组，可能值的集合也非常小。这也意味着有很多重复项。

示例:3, 10, 50, 10, 10, 3, 10, 3, 50, 3, 50, 50, 3, 10, 10, 50, 3, 3, 10, 50, 50, 3 .. .

不同/唯一值的集合是 {3, 10, 50}，即使数据收集要大得多，也非常小。

如果您打算对数组进行排序，您只需执行一次扫描即可计算值的出现次数:

3 : 8 occurences
10: 7 occurences
50: 7 occurences

然后排序就很简单了:只需输入 3 次“8”、7 次“10”和 7 次“50”。如果你还有其他列，仅仅统计出现次数是不够的，你必须建立一个索引，但想法是一样的。