algorithm - 在线性时间内对 [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. 创建列表中有多少不同项的映射，并保留每个项的计数(基本上是键的字典/ HashMap ，计数)
   • 这是对输入列表的单次迭代，所以 O(n) 步。
2. 根据键对上述大小为 log(n) 的元组列表进行排序。
   • 假设我们使用归并排序，那么归并排序的时间复杂度是k*log(k)，其中k是输入的大小。
   • 用log(n)替换k，我们得到这一步的复杂度为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) 时间内运行。