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

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

首先，您可以将数据放入主存储器吗？如果不能，那么您将需要依赖外部排序算法。这些算法通常基于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确实需要大量辅助内存，这就是为什么如果您要排序的数据量很大，可能不想使用它的原因之一。不过，由于它的变体被广泛使用，因此值得了解。）