Nad*_*ahu 5 sorting algorithm big-o
我试图解决以下任务:我给了一个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)更好,这是所需要的.
我认为您使用哈希表的方法是正确的，但我认为您不应该将元素插入哈希表，然后再次将它们复制出来。您应该仅使用哈希表来计算每个不同值的元素数量。
接下来，通过按顺序遍历所有值并将前一个元素的计数添加到其起始索引来计算每个不同值的起始索引：
i= 元素的起始索引i-1+ 元素的计数i-1。此步骤需要对k哈希表中的元素进行排序，这相当于 O(k log k) = O(log n log log n) 次操作，远小于步骤 1 和 3 的 O(n) 操作。
最后，再次遍历输入数组，在表中查找它，并找到它在输出数组中的位置。您复制该元素，并增加其值元素的起始索引，以便在其之后复制下一个元素。
如果项目的比较值是连续的整数（或者某个小范围内的整数），那么可以使用数组而不是哈希表来计数。
这称为计数排序。