algorithm - 排序时 "few-unique"是什么意思？

Question

全部。

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

在上面的站点，快速排序3路分区算法，我发现了4种不同的情况。我理解随机的、几乎排序的、颠倒的案例。但什么是“少数独特”？？？这意味着大整数键？？你能详细说明一下吗？谢谢。

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”。如果你有其他列，只计算出现次数是不够的，你必须建立一个索引，但思路是一样的。