为什么不总是使用堆排序

Question

该堆排序排序算法似乎有O(nlogn)的最差情况的复杂性,并且使用O(1)排序操作空间.

这似乎比大多数排序算法更好.那么,为什么不总是使用Heap Sort作为排序算法(为什么人们使用排序机制,如Merge sort或Quick sort)？

此外,我看到人们使用Heap排序中的"不稳定"一词.这意味着什么？

Answer 1

稳定排序可维护具有相同键的项的相对顺序.例如,假设您的数据集包含具有员工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 vs. Quicksort的情况下,事实证明有些方法(例如,中位数为5)使Quicksort的最坏情况非常罕见.此外,维护堆不是免费的.

给定一个具有正态分布的数组,Quicksort和Heapsort都将运行O(n log(n)).但是Quicksort的执行速度会更快,因为它的常数因子小于Heapsort的常数因子.简单来说,分区比保持堆快.

Answer 2

该堆排序具有的最差情况的复杂性O(n log(n)).然而实证研究表明,通常快速排序(和其他排序算法)比堆排序快得多,尽管其最坏情况的复杂性是O(n²):http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

另外,从维基百科上的快速排序文章:

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

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

Stackoverflow上的源代码:Quicksort vs heapsort

Answer 3

没有银弹......

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

如果您的数据集非常庞大并且不适合内存,那么合并排序就像魅力一样.它经常用于集群,其中数据集可以跨越数百台机器.