为什么不使用堆排序总是 [英] Why not use heap sort always

问题描述

在堆排序排序算法似乎有O（nlogn）最坏情况的复杂性，并且使用O（1）空间排序操作。

The Heap Sort sorting algorithm seems to have a worst case complexity of O(nlogn), and uses O(1) space for the sorting operation.

这似乎比大多数排序算法更好。那么，为什么不一次使用堆排序始终作为一个排序算法（以及为什么人们使用像合并排序或快速排序排序机制）？

This seems better than most sorting algorithms. Then, why wouldn't one use Heap Sort always as a sorting algorithm (and why do folks use sorting mechanisms like Merge sort or Quick sort)?

另外，我还看到有人使用术语不稳定性与堆排序。这是什么暗示？

Also, I have seen people use the term 'instability' with Heap sort. What does that imply?

推荐答案

有一个稳定的排序认为具​​有相同的关键项目的相对顺序。例如，假设你的数据集包含具有雇员ID和姓名记录。最初的顺序是：

A stable sort maintains the relative order of items that have the same key. For example, imagine your data set contains records with an employee id and a name. The initial order is:

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

您想按名称排序。一个稳定的排序将安排在此订单中的项目：

You want to sort by name. A stable sort will arrange the items in this order:

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

请注意，对于乔治的重复记录是在相同的相对次序，因为他们是在初始列表。同样的，两个吉姆的记载。

Note that the duplicate records for "George" are in the same relative order as they were in the initial list. Same with the two "Jim" records.

这是不稳定的排序可以安排这样的项目：

An unstable sort might arrange the items like this:

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

堆排序是不稳定的，因为在堆上操作可以改变等于项的相对顺序。不是所有的快速排序实现稳定。这取决于你如何实现分区。

Heapsort is not stable because operations on the heap can change the relative order of equal items. Not all Quicksort implementations are stable. It depends on how you implement the partitioning.

虽然堆排序有 0的最坏情况下的复杂性（N的log（n）），这并不能说明整个故事。在现实世界的实施中，有一些理论分析没有考虑到恒定的因素。在堆排序与快速排序的情况下，事实证明，有一些方法（5位数，例如），使快速排序的最坏的情况的确非常的少见。此外，维持堆是不自由的。

Although Heapsort has a worst case complexity of O(n log(n)), that doesn't tell the whole story. In real-world implementation, there are constant factors that the theoretical analysis doesn't take into account. In the case of Heapsort vs. Quicksort, it turns out that there are ways (median of 5, for example) to make Quicksort's worst cases very rare indeed. Also, maintaining a heap is not free.

由于具有正态分布的阵列，快速排序和堆排序将在 0无论运行（N的log（n））。但是，快速排序会执行得更快，因为它的持续性因素比不变因素堆排序更小。简单地说，分区比维护堆得更快。

Given an array with a normal distribution, Quicksort and Heapsort will both run in O(n log(n)). But Quicksort will execute faster because its constant factors are smaller than the constant factors for Heapsort. To put it simply, partitioning is faster than maintaining the heap.

这篇关于为什么不使用堆排序总是的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！