<分区>
我到处都读到堆排序的时间复杂度在最坏的情况下是O(nlog(n))。但我们也到处都读到，认为堆是在 O(nlog(n)) 中构建的是一种常见的误解。相反，您可以在 O(n) 中创建一个堆。所以考虑到一个堆可以在O(n)中做出来，看看下面的排序算法，告诉我在分析它的时间复杂度时我错在哪里。
- 将
n个元素放入堆中(时间:O(n)) - 直到堆为空，弹出每个元素并将其复制到一个数组中。 (时间:
O(n)。为什么？因为以同样的方式，所有元素都可以在O(n)中放入堆中，也可以提取所有元素在O(n)中。对吧？)。
总而言之，复杂度是 O(n)+O(n) 即 O(n)。但是在这里，我们还需要额外的O(n)内存。
我知道传统堆排序的时间复杂度为O(nlog(n))，内存复杂度为O(1)。但这不也是堆排序吗？与传统的堆排序算法不同，即使在最坏的情况下，它也能提供 O(n)。