<分区>
Heap Sort 排序算法的最坏情况复杂度似乎为 O(nlogn)，并且使用 O(1) 空间进行排序操作。
这似乎比大多数排序算法都要好。那么，为什么人们不总是将堆排序用作一种排序算法(以及为什么人们使用像归并排序或快速排序这样的排序机制)？
另外，我看到人们在堆排序中使用术语“不稳定”。这意味着什么？
<分区>
Heap Sort 排序算法的最坏情况复杂度似乎为 O(nlogn)，并且使用 O(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
堆排序不稳定，因为对堆的操作会改变相等项的相对顺序。并非所有 Quicksort 实现都是稳定的。这取决于您如何实现分区。
尽管 Heapsort 的最坏情况复杂度为 O(n log(n))，但这并不能说明全部情况。在现实世界的实现中，存在理论分析未考虑的常数因素。在 Heapsort 与 Quicksort 的情况下，事实证明有一些方法(例如，中位数为 5)可以使 Quicksort 的最坏情况确实非常罕见。此外，维护堆也不是免费的。
给定一个服从正态分布的数组，Quicksort 和 Heapsort 都将在 O(n log(n)) 内运行。但是 Quicksort 会执行得更快，因为它的常数因子小于 Heapsort 的常数因子。简单来说，分区比维护堆更快。
关于algorithm - 为什么不总是使用堆排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8311090/