排序问题？

Question

堆排序被视为“分而治之”排序还是优先队列排序？

此外，冒泡排序适合什么类别(除了可怕的排序之外)。

我读到，堆排序通常被认为是“分而治之”排序，但它可以是优先级队列排序。严格来说是其中之一还是另一个？或者两者都是怎样的？我找不到任何关于冒泡排序的信息。

Answer 1

我不认为 HeapSort 被认为是“分而治之”，因为算法会立即将问题分割为子问题。为了进行堆排序，算法执行 ExtractMin 或 ExtractMax 直到堆为空。这些操作的复杂度为 O(logn)，因为在每个 ExtractMin 或 ExtractMax 之后，Heap 必须执行 Heapify 来保持它的偏序。最后的成本为 O(nlogn)，因为它执行 n ExtractMin 或 ExtractMax。

这是一个伪代码

HeapSort()
 heap
 new_ ordered_collection
 while(heap.NotEmpty)
   new_ ordered_collection.add(heap.ExtractMin)//or ExtractMax
   heap.Heapify //could be MaxHeapify or MinHeapify
 return new_ ordered_collection

请注意，ExtractMin 和 ExtractMax 会弹出堆的最小或最大元素。

如您所见，我没有看到“分而治之”的策略。

但是heap.Heapify根据堆的偏序对元素重新排序。这个定义了每个节点与其两个子节点之间的关系，因此，heap.Heapify 应用了“分而治之”策略，但这是 DataStructre 本身的问题，与算法无关。

冒泡排序是一种简单算法。