为什么不使用堆sorting总是

堆分类sortingalgorithm似乎具有O(nlogn)的最坏情况复杂度,并使用O(1)空间进行sorting操作。

这似乎比大多数sortingalgorithm更好。 那么,为什么没有人总是使用堆sorting作为sortingalgorithm(以及为什么人们使用sorting机制,如合并sorting或快速sorting)?

另外,我也看到人们用Heapsorting来使用术语“不稳定性”。 这意味着什么?

稳定的sorting维护具有相同键的项目的相对顺序。 例如,假设您的数据集包含带有员工ID和姓名的logging。 最初的顺序是:

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

你想按名称sorting。 一个稳定的sorting将安排在这个顺序的项目:

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

请注意,“George”的重复logging与最初列表中的相同顺序相同。 与两个“吉姆”logging相同。

不稳定的sorting可能会安排这样的项目:

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

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

尽pipeHeapsort的复杂度最低,为O(n log(n)) ,但并不能说明整个情况。 在现实世界中,理论分析中没有考虑到常量因素。 在Heapsort vs. Quicksort的情况下,事实certificate,有些方法(例如,中间值为5)使得Quicksort最糟糕的情况确实非常罕见。 另外,维护一个堆不是免费的。

给定一个正态分布的数组,Quicksort和Heapsort都将以O(n log(n)) 。 但Quicksort会执行得更快,因为它的常数因子小于Heapsort的常数因子。 简而言之,分区比维护堆更快。

堆sorting的最坏情况复杂度为O(n log(n)) 。 然而,实证研究表明,尽pipe最坏情况的复杂度是O(n²) ,但一般的快速sorting (和其他sortingalgorithm)比堆sorting快得多: http : //www.cs.auckland.ac.nz/~jmor159/PLDS210 /qsort3.html

另外,从维基百科的快速sorting文章 :

quicksort最直接的竞争对手是heapsort。 Heapsort最糟糕的运行时间总是O(n log n)。 但是,heapsort被认为平均比标准就地quicksort慢一点。 这仍然是争论和研究,一些出版物表明相反。[13] [14] Introsort是一种快速sorting的变体,当检测到一个不好的情况时可以切换到堆sorting,以避免快速sorting的最坏情况下的运行时间。 如果事先知道heapsort是必要的,直接使用它将比等待introsort切换到它更快。

但是,快速sorting不应该用于需要保证响应时间的应用程序!

来源Stackoverflow: Quicksort vs heapsort

没有银子弹

只是提到另一个我还没有看到的论点:

如果你的数据集真的很大,不适合内存,那么合并sorting就像一个魅力。 它经常用于数据集可以跨越数百台机器的集群。

稳定的sortingalgorithm保持相同键的logging的相对顺序

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

至于你断言“人们使用sorting机制,如合并sorting或快速sorting”我敢打赌,大多数人使用任何内置到他们的语言,不要考虑sortingalgorithm。 那些推出自己的可能没有听说过堆sorting(最后是个人经验)。

最后一个也是最大的原因是不是每个人都想要一个sorting的堆。 有些人想要sorting的列表。 如果一般的Joe程序员的老板说“对这个列表进行sorting”,Joe说:“这是你从未听说过的这个堆数据结构,老板!”,Joe的下一次性能评估不会那么好。

当我在80年代中期在Tandem Non-Stop计算机上工作很短时间时,我注意到系统内核sorting例程是HeapSort,正是因为它确保了NlogN性能。 但是,我不知道谁有什么理由使用它,所以我不知道它在实践中是如何工作的。 我喜欢大堆,但是除了上面提到的缺点之外,我听说它使用了现代化的存储器,因为它使得存储器访问遍布整个地方,而快速sorting甚至小基数sorting最终混合了一个相对较小的数字连续读取和写入stream – 所以caching更有效。