0

在哪些情况下可以使用堆排序？众所周知，堆排序的复杂度为n× lg(n)。但它的使用频率远低于快速和合并排序。那么我们什么时候准确地使用这种堆排序，它的缺点是什么？

4

3 回答 3

1

堆排序的特点

  • O(nlogn) 时间最佳、平均、最坏情况性能
  • O(1) 额外内存

在哪里使用它？

  • 保证 O(nlogn) 性能。当您不一定需要非常快的性能，但保证 O(nlogn) 性能（例如在游戏中）时，因为 Quicksort 的 O(n^2) 可能会非常缓慢。那为什么不使用 Mergesort 呢？因为它需要 O(n) 额外的内存。
  • 为了避免快速排序的最坏情况。C++ 的std::sort例程通常使用称为 Introsort 的 Quicksort 变体，如果 Quicksort 递归太深，则使用 Heapsort 对当前分区进行排序，表明发生了最坏的情况。
  • 即使突然停止，也是部分排序的数组。如果 Heapsort 突然停止，我们会得到一个部分排序的数组。可能有用，谁知道呢？

缺点

  • 与快速排序相比相对较慢
  • 缓存效率低下
  • 不稳定
  • 不是真正的自适应（如果给定一些排序数组，不会变得更快）
于 2013-09-10T18:05:59.433 回答
0

根据排序算法的维基百科文章， Heapsort 和 Mergesort 似乎在O(n log n)最佳、平均和最坏情况下都具有相同的时间复杂度。

快速排序有一个缺点，因为它的最坏情况时间复杂度为(a)。O(n2)

Mergesort的缺点是它的内存复杂度是O(n)，而 Heapsort 是O(1)。另一方面，Mergesort 是一种稳定的排序，而 Heapsort 不是。

所以，基于此，如果我不关心排序的稳定性，我会优先选择Heapsort而不是Mergesort，以尽量减少内存使用。如果需要稳定性，我会选择 MergeSort。

或者，更准确地说，如果我有大量数据要排序，并且我必须编写自己的算法来完成它，我会这样做。对于绝大多数情况，两者之间的差异是无关紧要的，直到您的数据集变得庞大。

事实上，我什至在没有提供其他排序的实际生产环境中使用冒泡排序，因为：

  • 它非常容易编写（即使是优化版本）；
  • 如果数据具有某些属性（在添加几个项目之前已经大部分排序的小数据集或数据集），它就足够有效了。

喜欢goto和多个返回点，即使是看似糟糕的算法也有它们的位置:-)

(a)而且，在您想知道为什么 C 使用效率较低的算法之前，它没有（必然）。尽管有这个qsort名字，但并没有强制要求它在幕后使用 Quicksort - 这是一个常见的误解。它很可能使用其他算法之一。

于 2013-08-13T09:16:01.120 回答
0

请注意，无论数组是否已经按升序或降序部分排序，堆排序的运行时间复杂度都与 O(n log n) 相同。

请参阅以下链接以进一步说明相同的大 O 计算： https ://ita.skanev.com/06/04/03.html

于 2017-10-27T07:07:12.090 回答