排序方法不是如此混乱的数据

Question

我想排序一百万个数字。我已经把它们放在了记忆里（我们假设它们是合适的），而且我知道一个事实，任何给定的数字最初都处于非常接近它的排序位置的位置（即原始数据中的第1000个数字将会非常接近它的最终位置非常可能在分拣后在900和1100位之间结束）。

哪种排序方法在这种情况下表现最好？而最重要的是，为什么它会比其他人表现更好？假设内存对于任何常见方法都足够大。

Answer 1

如果您在n个元素上运行原始插入排序，那么它们将在时间O（nk）中运行，这些元素的最终位置上最多为k个点。许多排序算法，特别是introsort，通过让排序算法一旦元素足够接近就停止排序，然后切换到插入排序来使用这个事实。由于插入排序在大O中隐藏的常量因子非常低，所以我怀疑它在这里会工作得很好。