1回答

liuyubobobo

2021-08-04

已采纳

首先， heapify 是 O(n) 的，但是堆排序不是 O(n) 的。heapify 只是堆排序的一步而已，heapify 将一个数组整理成堆的形式，但是一个堆不是一个排序数组，从一个堆到一个排序数组，需要一个过程，请再理解一遍堆排序的整个过程。堆排序算法也是 O(nlogn) 的。

其次，是的，堆排序虽然时间复杂度也是 O(nlogn) 的，但整体性能就是不如快排和归并排序的。所以基本上不会有语言的标准库用堆排序来实现排序算法。堆排序是对的一个应用，但不是主要应用。堆的最主要的应用，是优先队列这种数据结构。

最后，就算是一个复杂度更优的算法，比如一个 O(n) 的算法，其实际性能差于一个 O(nlogn) 的算法，也是正常的。因为复杂度描述的是随着 n 的增大整个算法性能的增长趋势。但是忽略了诸多常数或者低阶项的开销。这也就是为什么，虽然有 O(n) 级别的非比较排序，但实际上，除了一些特殊情况，我们并不会使用这些 O(n) 的排序算法的原因。因为他们在大多数场景下，实际性能反而不如诸如快排这样的 O(nlogn) 的排序。

继续加油！：）

0

1

慕运维6075306

非常感谢！

2021-08-05

共1条回复