我在算法课上遇到问题。问题指出：
假定给定一个由n个整数组成的数组，范围为{1，...，logn ** logn}。显示如何在时间O（nloglogn）排序此数组。
这是每周一次的作业，本周我们主要处理堆排序和计数排序。乍一看，我看到有一个范围，所以我尝试对排序进行计数....但是范围太大。计数排序为O（n + k），其中k为范围。这里logn ** logn大于所需的nloglogn。所以我感到迷茫。因此，可以肯定地说，我们不能使用比较排序，因为它被限制在O（n logn）以下。谁能帮忙？
为了使时间复杂度为O（n log（log（n（n））），基数基数必须为n。
使用log2（），n = 2 ^ 16 = 65536，log2（n）= 16，范围是1到16 ^ 16 = 2 ^ 64。使用基数排序基数= n = 2 ^ 16 = 65536，基数排序需要log2（log2（2 ^ 16））= 4遍。]
使用log3（），n = 3 ^ 9 = 19683，范围是1到9 ^ 9 = 3 ^ 18。使用基数排序基= n = 3 ^ 9，需要进行log3（log3（3 ^ 9））= 2遍以进行基数排序。