This question already has answers here:
Quicksort vs heapsort
(12个答案)
Quicksort superiority over Heap Sort
(5个答案)
6年前关闭。
堆排序排序算法似乎具有O(nlogn)的最坏情况复杂度，并使用O(1)空间进行排序操作。
这似乎比大多数排序算法要好。然后，为什么不总是使用堆排序作为排序算法(以及为什么人们使用诸如合并排序或快速排序之类的排序机制)？
另外，我看到人们在堆排序中使用术语“不稳定性”。这意味着什么？
您想按名称排序。稳定的排序将按以下顺序排列项目:
请注意，“George”的重复记录的相对顺序与初始列表中的相对顺序相同。与两个“Jim”记录相同。
不稳定的排序可能会这样排列项目:
堆排序不稳定，因为堆上的操作可以更改相等项目的相对顺序。并非所有Quicksort实现都是稳定的。这取决于您如何实现分区。
尽管Heapsort最糟糕的情况是
给定一个具有正态分布的数组，Quicksort和Heapsort都将在
(12个答案)
Quicksort superiority over Heap Sort
(5个答案)
6年前关闭。
堆排序排序算法似乎具有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的常量因子。简而言之，分区比维护堆快。