这不是我的家庭作业。这是我自己的作业，我是自学算法。
在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 正在寻找的是第二种方法，对吧？
谢谢
最佳答案
我们可以创建一个 HashMap ，将每个元素存储为键，将其频率存储为值。
使用任何排序算法在 log(n)*log(log(n)) 时间内(即 (klogk))对这张 map 进行排序。
现在 扫描 HashMap 并将元素添加到新数组的频率次数。像这样:
total time = 2n+log(n)*log(log(n)) = O(n)
关于算法 - 对具有 LogLogN 个不同元素的数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9964240/