为什么不总是使用堆排序

Question

堆排序算法的最坏情况时间复杂度似乎是O(nlogn)，并且在排序操作中使用O(1)空间。这似乎比大多数排序算法要好。那么为什么不总是使用堆排序作为排序算法呢（人们为什么会使用归并排序或快速排序等排序机制）?

此外，我见过人们在堆排序中使用术语“不稳定”。这意味着什么？

- Saket

---

请查看以下链接以了解有关编程的内容：快速排序优于堆排序，何时使用每种排序算法？ - Nick Dandoulakis

我同意与上述问题的相似之处，但不同意其中的重复。它更多地涉及对堆排序和快速排序进行比较，而不是对堆排序进行一般性分析（包括其优缺点，如果有的话）。 - Saket

在某些情况下，我们不要忘记稳定排序的要求（堆排序和快速排序通常是不稳定的 - 归并排序通常是稳定的）。 - hugomg

我仍然坚信，这些信息可以在几乎任何搜索引擎上轻松找到（提示：使用谷歌）。 - ScarletAmaranth

我在网上找到了一些评论/答案，但是我还没有得到令人信服和清晰的答案。因此，SO！ - Saket

Answer 1

稳定排序维护了具有相同键的项目的相对顺序。例如，想象一下您的数据集包含具有员工ID和姓名的记录。初始顺序为：

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

您想按名称排序。稳定排序将按以下顺序排列项目：

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

请确认以下翻译是否符合要求：

请注意，“George”重复的记录与它们在初始列表中的相对顺序相同。两个“Jim”记录也是如此。

而不稳定的排序可能会像这样排列项目：

如果符合要求，请回复“确认”。

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

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

尽管Heapsort的最坏情况复杂度为O(n log(n))，但这并不能说明全部。在实际应用中，存在常数因素，理论分析无法考虑到这些因素。在Heapsort和Quicksort之间，事实证明可以通过某些方法（例如5个中位数），使Quicksort的最坏情况非常罕见。此外，维护堆不是免费的。

对于具有正常分布的数组，Quicksort和Heapsort都将以O(n log(n))运行。但是Quicksort将更快，因为其常数因子小于Heapsort的常数因子。简单来说，分区比维护堆更快。

- Jim Mischel

---

快速排序相比堆排序更好地利用缓存（引用局部性），从而增加了收益，而堆排序则无法从中获得收益。 - cobie

快速排序和归并排序比堆排序更容易并行化。 - Chinasaur

我认为稳定性只有在需要相同顺序的解决方案时才有用。稳定性并不会使一个解决方案在复杂度方面比其他解决方案更好。 - Sanjeev Kumar Dangi

现在为什么会有人对这个答案进行负评？OP问的是堆排序中稳定性的含义，这个回答有没有回答到这个问题呢？还是我在解释时犯了错误？ - Jim Mischel

Answer 2

堆排序的最坏时间复杂度为O(n log(n))。然而经验研究表明，通常情况下，快速排序（和其他排序算法）比堆排序要快得多，尽管其最坏时间复杂度为O(n²)：http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html 此外，从维基百科上的快速排序文章可以看到：

快速排序的最直接竞争对手是堆排序。堆排序的最坏运行时间始终为O(n log n)。但是，堆排序被认为平均比标准原地快速排序略慢。这仍在研究中，并且有些出版物表明相反[13][14]。Introsort是快速排序的一种变体，当检测到坏情况时切换到堆排序以避免快速排序的最坏运行时间。如果事先知道需要堆排序，则直接使用它比等待introsort切换到堆排序更快。

然而，在需要响应时间保证的应用程序中，永远不应使用快速排序！

Stackoverflow上的来源：Quicksort vs heapsort

- Jean Logeart

---

我在网上找到了类似的评论/答案，但是我还没有得到令人信服和清晰的答案。 - Saket

快速排序具有更好的缓存行为，这就是它经验证明更快的原因。 - Thomas Jungblut

当你比较这两种排序算法时，我假设堆排序的O(1)空间已经被考虑进去了？有人能解释一下空间吗？ - Allan C

Answer 3

没有万能的解决办法...

还有一个观点我在这里还没看到：

如果你的数据集非常巨大，无法放入内存中，那么归并排序是一个很好的选择。它经常用于数据跨越数百台机器的集群。

- Karoly Horvath

Answer 4

稳定的排序算法可以保持具有相等键的记录的相对顺序。

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

至于你声称“人们使用像归并排序或快速排序这样的排序机制”，我敢打赌，大多数人使用他们语言内置的任何东西，并不太考虑排序算法。那些自己编写代码的人可能从未听说过堆排序（最后一个是个人经验）。

最后一个也是最重要的原因是，并不是每个人都想要一个排序的堆。有些人想要排序列表。如果普通的程序员老板说“给这个列表排序”，而Joe说“这里有一个您从未听说过的堆数据结构，老板！”，那么Joe的下一个绩效评估将不会太好。

- Kane

---

当涉及到排序算法时，不稳定性意味着您不会改变相同比较的事物的顺序。这是完全不同的事情。 - hugomg

好的，我完全错了。我已经编辑了我的答案来更正它。 - Kane

Heapsort（堆排序）和快速排序一样，是一种原地排序算法。数组被重组成一个堆，然后再按照顺序重新排列。使用堆排序不会导致“你从未听说过的堆数据结构”。请参见 http://en.wikipedia.org/wiki/Heapsort。 - Jim Mischel

虽然如果你从一个链表开始，想要得到一个链表，使用HeapSort可能不是最好的选择，我想。 - Vatine

@Vatine：但是你也不会想在链表上使用快速排序。归并排序来拯救。 - Jim Mischel

@JimMischel: 确实如此。 - Vatine

Answer 5

当我在80年代中期短暂地使用Tandem Non-Stop计算机时，我注意到系统中核心的排序例程是HeapSort，因为它能够确保NlogN的性能。但我不知道是否有人有任何理由使用它，因此我不知道它在实践中如何工作。我喜欢堆排序，但除了上面提到的缺点外，我听说它利用现代内存的效果不佳，因为它使内存访问到处都是，而快速排序甚至是小的基数排序最终会交错着相对较少的连续读写流——因此缓存更有效。

- mcdowella