哪种排序算法最适合非常大的数据集

我在Internet上搜索以找到最适合于非常大的数据集的排序算法。我发现许多人认为合并排序是最好的，因为它是公平的，并且它可以确保时间复杂度为O（n log

n）并且快速排序是不安全的：诚然，快速排序的变体也可以不安全，因为实际数据集可以是任何数据。

如果交换两个元素的时间成本可以忽略不计，那么为什么在这种情况下为什么不能选择堆排序作为最佳排序算法呢，因为它与O（n log n）一样就位了？

在合并排序的情况下，它需要另一个O（n）空间；如果数据非常大，则无法使用此算法。

请告诉我：在这种情况下哪种算法最好？

没有一种算法显然是“最佳”算法。这取决于许多因素。

首先，您可以将数据放入主存储器吗？如果不能，那么您将需要依赖外部排序算法。这些算法通常基于quicksort和mergesort。

其次，您对您的输入分配了解吗？如果大多数数据是经过排序的，那么像Timsort之类的东西可能是一个不错的选择，因为它被设计为可以很好地处理已排序的数据。如果大多数情况下是随机的，那么Timsort可能不是一个好选择。

第三，您要排序哪种元素？如果要对通用对象进行排序，那么您几乎就只能进行比较排序。如果不是这样，也许您可以使用非比较排序，例如计数排序或基数排序。

第四，您有几个核心？一些排序算法（快速排序，合并排序，MSD基数排序）确实很好地并行化，而其他算法则没有（并行排序）。

第五，您的数据如何表示？如果将它们存储在数组中，则由于引用的局部性，quicksort或quicksort变体可能会做得很好，而由于需要额外的内存，mergesort可能会变慢。但是，如果它们在链表中，则来自quicksort的引用位置会消失，并且mergesort突然变得更具竞争力。

最好的选择可能是考虑很多不同的因素，然后从那里做出决定。设计和研究算法之所以如此有趣的原因之一是，几乎没有一个最佳选择。通常，最佳选择取决于您的具体情况，并根据您所看到的内容进行更改。

（您在总结此答案之前提到了有关quicksort，heapsort和mergesort的一些详细信息。在您没错的情况下，quicksort具有退化的O（n

2）最坏情况，但是有很多方法可以避免这种情况。introsort算法会跟踪递归深度，并在快速排序看起来退化时将其切换到堆排序，从而保证O（n log

n）最坏情况的行为以及较低的内存开销，并最大程度地提高您的收益。 quicksort。随机快速排序虽然仍然具有O（n

2）最坏的情况，但实际上碰到最坏情况的可能性却很小。

Heapsort在实践中是一个很好的算法，但是在某些情况下不如其他算法那么快，因为它没有很好的参考位置。也就是说，它永远不会退化并且仅需要O（1）辅助空间这一事实是一个巨大的卖点。

Mergesort确实需要大量辅助内存，这就是为什么如果您要排序的数据量很大，可能不想使用它的原因之一。不过，由于它的变体被广泛使用，因此值得了解。）