Kar*_*son 7 sorting algorithm mergesort time-complexity counting-sort
设计一个算法，对存在重复的n 个整数进行排序。不同数字的总数是k。你的算法应该有时间复杂度O(n + k*log(k))。预计时间足够了。对于k 的哪些值，算法变为线性？
我无法提出满足条件的整数排序算法，它必须是O(n + k*log(k))。我不是一个非常高级的程序员，但在这个人应该为xi列表中的所有数字提出一种算法之前，我遇到了问题0 ? xi ? m，该算法是 O(n+m)，其中 n 是列表中的元素数列表和 m 是列表中最大整数的值。我通过使用计数排序轻松解决了这个问题，但我在这个问题上很挣扎。对我来说最困难的k*log(k)条件是 ordo 表示法下的术语，如果n*log(n)相反，我将能够使用合并排序，对吗？但现在这是不可能的，所以任何想法都会非常有帮助。
提前致谢！
chq*_*lie 12
这是一个可能的解决方案：
使用哈希表，计算唯一值的数量和每个值的重复数量。这应该具有O(n)的复杂度。
枚举哈希表，将唯一值存储到临时数组中。复杂度是O(k)。
使用诸如归并排序之类的标准算法对该数组进行排序：复杂度为O(k.log(k))。
通过复制存储在哈希表中的每个唯一值的排序数组的元素来创建结果数组。复杂度是O(n) + O(k)。
组合复杂度为O(n + k.log(k))。
例如，如果k是一个小常数，则当n变得越来越大时，对n 个值的数组进行排序会向线性时间收敛。
如果在第一个阶段，k是递增计算的，k似乎没有明显小于n，则删除哈希表并使用标准算法对原始数组进行排序。