为什么不总是使用堆排序呢

小开

堆排序具有 O(n log(n))的最坏情况复杂性。然而，实证研究表明，一般来说，快速分类(和其他排序算法)比堆排序快得多，尽管它的最坏情况下的复杂度是 O(n²): http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

另外，来自维基百科上的快速分类文章快速分类文章:

快速排序最直接的竞争对手是堆排序。Heapsort 的最坏情况运行时间总是 O (n log n)。但是，假设堆排序平均比标准的就地快速排序慢一些。这仍然是辩论和研究，一些出版物表明相反。[13][14]内向排序是快速排序的一种变体，当检测到坏情况时，它会切换到堆排序，以避免快速排序的最坏情况运行时间。如果事先知道堆排序是必需的，那么直接使用它将比等待内部排序切换到它更快。

但是，在需要保证响应时间的应用程序中不应该使用快速排序！

关于堆栈溢出的来源: 快速排序 VS 堆排序

小开

没有什么灵丹妙药。

再提一个我还没见过的论点:

如果您的数据集非常庞大并且不适合内存，那么合并排序就非常有效。它经常用于数据集可以跨越数百台机器的集群中。

小开

稳定的排序算法用相同的键保持记录的相对顺序

一些应用程序喜欢有这种稳定性，大多数不在乎，例如谷歌是你的朋友。

至于你断言“人们使用像合并排序或快速排序这样的排序机制”，我敢打赌，大多数人使用他们的语言中内置的任何东西，并没有太多地考虑排序算法。那些自己卷的可能没有听说过堆排序(最后一个是个人经验)。

最后也是最大的一个原因是，并不是每个人都想要一个排序堆。有些人想要分类列表。如果普通程序员的老板说“对这个列表进行排序”，而 Joe 说“这是一个你从未听说过的堆数据结构，老板!”，乔的下一个业绩评估将不会是那么好。

小开

最佳答案

稳定排序维护具有相同键的项的相对顺序。例如，假设您的数据集包含具有雇员 ID 和名称的记录。最初的顺序是:

1, Jim
2, George
3, Jim
4, Sally
5, George

您希望按名称排序。稳定排序将按以下顺序排列项目:

2, George
5, George
1, Jim
3, Jim
4, Sally

注意，“ George”的重复记录的相对顺序与初始列表中的相对顺序相同。两张吉姆的唱片也一样。

一种不稳定的排序可能会这样安排项目:

5, George
2, George
1, Jim
3, Jim
4, Sally

堆排序不稳定，因为堆上的操作可以更改相等项的相对顺序。并非所有的 Quicksort 实现都是稳定的。这取决于如何实现分区。

尽管 Heapsort 具有 O(n log(n))的最坏情况复杂性，但这并不能说明全部问题。在现实世界的实现中，有许多理论分析没有考虑到的因素。在 Heapsort 和 Quicksort 的例子中，事实证明有很多方法(例如，中位数为5)可以使 Quicksort 的最坏情况变得非常罕见。另外，维护堆也不是免费的。

给定一个具有正态分布的数组，Quicksort 和 Heapsort 都将在 O(n log(n))中运行。但是 Quicksort 执行得更快，因为它的常数因子比 Heapsort 的常数因子小。简单地说，分区比维护堆更快。

小开

在80年代中期，当我在串联非停止计算机上工作了一小段时间时，我注意到系统内核排序例程是 HeapSort，正是因为它提供了有保证的 NlogN 性能。不过我不知道有谁有理由使用它，所以我不知道它在实践中是如何工作的。我喜欢堆排序，但是除了上面提到的缺点之外，我还听说它没有充分利用现代内存，因为它可以在任何地方访问内存，而快速排序甚至小基数排序最终会混合相对较少的连续读写流——所以缓存更有效。