c - 什么情况下我们使用堆排序？

Question

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

Answer 1

堆排序的特点

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

在哪里使用它？

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

缺点

• 与快速排序相比相对较慢
• 缓存效率低下
• 不稳定
• 并不是真正的自适应(如果给定某种排序的数组，速度不会变得更快)