排序问题？

Question

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

此外，冒泡排序适合哪种类型的排序（除了可怕的排序）。

我读过堆排序通常被认为是“分而治之”排序，但它可以是优先级队列排序。严格来说是一种还是另一种？或者两者兼而有之？我找不到关于冒泡排序可能被考虑的任何内容。

Answer 1

我不认为HeapSort被认为是“分而治之”，因为算法不会将问题细分为子问题。执行 HeapSort 算法执行ExtractMin或ExtractMax直到 Heap 为空。这些行动是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本身没有的算法。

冒泡排序是一种naive算法。