在线性时间内对 [log n] 不同值进行排序

Question

我有一个 n 个整数的数组，它只能假设log n 个可能的值（和任何值）。例如，在 中S = [349,12,12,283,349,283,283,12]，只有 3 个不同的数字(log 8 = 3)。

我必须在短时间内对这个数组进行排序O(nlogn)。我应该使用哪种算法？也许基数排序和计数排序？它的分析呢？

Answer 1

由于假定只有log(n)唯一元素，因此您可以O(n)使用以下算法及时获得排序列表：

1. 创建列表中有多少不同项目的映射，并保留每个项目的计数（基本上是键的字典/哈希图，计数）
   • 这是对输入列表的一次迭代，所以O(n)步骤。
2. log(n)根据键对上述大小的元组列表进行排序。
   • 假设我们使用归并排序，那么归并排序的时间复杂度为k*log(k)，其中k是输入的大小。
   • 替换k为log(n)，我们得到这一步的复杂度为O(log(n)*log(log(n)))。
   • 由于在复杂性方面，O(log(n)*log(log(n)))< O(n)，所以直到这一步的整体复杂性是O(n) + O(log(n)*log(log(n)))，这相当于O(n)再次。
3. 迭代已排序的键，并使用单个 for 循环生成排序列表，其中每个值按其计数重复。这里将有最大O(n)迭代。

所以总的来说，上面的算法将在 O(n) 时间内运行。