algorithm - 在 O(n log(log n)) 中对数组进行排序

Question

我正在尝试解决以下作业: 我得到了一个包含 n 个元素的数组。众所周知，并非数组的所有键都是不同的，但假设我们有 k 个不同的元素(当然是 k<=n)。 分配是在 O(n log(log n)) 最坏情况下对数组进行稳定排序，同时 k=O(log n)。我可以使用 O(n) 的额外内存。

我目前的解决方案描述如下:

---

创建一个大小为 k 的链式哈希表，它执行以下操作: 如果哈希函数试图将一个元素插入到一个已经有值的地方——它检查它们是否相等——如果相等，它就把它添加到列表中，如果不相等，它就开始在数组中移动，直到找到一个位置具有相同值或空白空间(以先到者为准)。

这样，每个地方的列表只包含具有相同键的元素。哈希表的插入是从头到尾在原始数组中进行的，因此每个列表都是稳定排序的。 然后使用 mergeSort 对哈希表中的数组进行排序(对于列表，我们将第一个元素视为一个元素并移动它)。

完成合并排序后，我们按顺序将元素复制回原始数组，每当遇到列表时，我们按顺序复制每个元素。

以下是我不确定的地方:

可以这么说吗，因为哈希表的大小是 k，而我们只有 k 个不同的元素，统一哈希法保证哈希函数尝试在数组中的同一位置给出不同值的时间可以忽略不计，并且因此它的构建时间复杂度是 O(n)？

因为如果是这样的话，算法的运行时间似乎是 O(n + k log k) = O(n + log n*log(log n))。 这绝对比所需的 O(n log k) 更好。

Answer 1

我认为您在哈希表方面走在了正确的轨道上，但我认为您不应该将元素插入到哈希表中，然后再将它们复制出来。您应该仅使用哈希表来计算每个不同值的元素数量。

接下来，通过按顺序遍历所有值并将前一个元素的计数添加到其起始索引，计算每个不同值的起始索引:

• 元素 i 的起始索引 = 元素 i-1 的起始索引 + 元素 i-1 的计数。

这一步需要对哈希表中的k元素进行排序，相当于O(k log k) = O(log n log log n)操作，比O(n)少很多对于步骤 1 和 3。

最后，您再次遍历您的输入数组，在表中查找它，并找到它在输出数组中的位置。您复制该元素，并增加其值的元素的起始索引，以便在它之后复制下一个元素。

如果项目的比较值是连续的整数(或某个小范围内的整数)，那么可以用数组代替哈希表进行计数。

这叫做 counting sort .