如何排序比n log n更快(在列表中给出一个强大的条件)？

Question

我提出以下问题(didn`t知道如何解决它所有的方法)给定一个阵列ARR的ñ int小号,我们需要理清it.We已经知道ķ的这个intS被放置在原来的ARR作为排序数组.(只是不知道他们中的哪一个)他们告诉我这样的排序要好得多nlogn- 我没有任何线索......任何建议？

Answer 1

关键事实是您正在处理整数并且您知道最大的键，这正是使用基数排序并且其复杂性是线性的。

还有第二种方法，如果其中 k 个已经排序，您可以使用某种版本的 shell 排序和序列，这将产生最佳结果

我真的不知道 shell-sort 在这里有什么帮助 - 你最终只会移动已经排序的元素，并且提到 k-already-in-the-正确位置，基数排序显然不是什么本来打算使用的。 (3认同)
据我所知，当我们知道数字范围时，基数排序会有所帮助 - 在这里我们没有。 arr 的元素是整数（任何）我们只知道这个元素中的 k 被放置在排序后将保留的位置 (2认同)

Answer 2

如果我们不知道：

没有比?(nlog(n))在最坏的情况下我们可以做得更好的选择。

为什么：

放好k=1，祝你好运...
这么说吧，k=0.9n让 k 个元素放在前面。即使我们知道它们在前面，那么我们仍然需要对 size 的数组进行排序0.1n，因此在最坏的情况下我们需要0.1*n*log(0.1*n)=0.1*n*(log(0.1)+log(n))=0.01*nlog(n)-0.1*n比较，即?(n*log(n)).

当然，这只是最坏情况下的理论结果。在实践中，k正确位置上有确切元素的信息可以显着限制要完成的工作量。但可以肯定的是，我们需要更多地了解k和n（或至少假设某事）。