算法 - 对具有 LogLogN 个不同元素的数组进行排序

Question

这不是我的家庭作业。这是我自己的作业，我是自学算法。

在Algorithm Design Manual , 有这样的消费税

4-25 Assume that the array A[1..n] only has numbers from {1, . . . , n^2} but that at most log log n of these numbers ever appear. Devise an algorithm that sorts A in substantially less than O(n log n).

我有两种方法:

---

第一种方法:

基本上我想对这个问题进行计数排序。我可以先扫描整个数组 (O(N)) 并将所有不同的数字放入一个 loglogN 大小的数组 (int[] K)。

然后应用计数排序。但是，在设置计数数组 (int[] C) 时，我不需要将其大小设置为 N^2，而是将大小也设置为 loglogN。

但这样一来，当计算每个不同数字的频率时，我必须扫描数组 K 以获得该元素的索引 (O(NloglogN)，然后更新数组 C。

---

第二种方法:

同样，我必须扫描整个数组以获得大小为 loglogN 的不同数字数组 K。

然后我只是做一种类似于快速排序的操作，但是分区是基于 K 数组的中位数(即，每次主元是 K 数组的元素)，递归地进行。

我认为这种方法最好，复杂度为 O(NlogloglogN)。

---

我说的对吗？或者有更好的解决方案？

Algorithm Design Manual 中有类似的练习，例如

4-22 Show that n positive integers in the range 1 to k can be sorted in O(n log k) time. The interesting case is when k << n.

4-23 We seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is O(log n). Give an O(n log log n) worst-case time algorithm to sort such sequences.

但基本上对于所有这些练习，我的直觉总是想到计数排序，因为我们可以知道元素的范围，并且与整个数组的长度相比，该范围足够短。但经过更深入的思考，我猜想 excise 正在寻找的是第二种方法，对吧？

谢谢

Answer 1

我们可以创建一个 HashMap ，将每个元素存储为键，将其频率存储为值。

使用任何排序算法在 log(n)*log(log(n)) 时间内(即 (klogk))对这张 map 进行排序。

现在 扫描 HashMap 并将元素添加到新数组的频率次数。像这样:

total time = 2n+log(n)*log(log(n)) = O(n)