排序问题？(Sorting questions?)

排序问题？(Sorting questions?)

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

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

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

Is a heap sort considered a "divide and conquer" sort or a priority queue sort?

Also, what category of sort would a bubble sort fit into (other than horrible).

I've read that a heap sort is generally considered a "divide and conquer" sort, but it can be a priority queue sort. Is it strictly one or the other? Or is it some how both? I cannot find anything on what a bubble sort may be considered.

最满意答案

我不认为HeapSort被认为是“分而治之”，因为算法不会将问题细分为子问题。 要执行HeapSort算法执行ExtractMin或ExtractMax，直到Heap为空。 这些操作是O(logn)因为在每个ExtractMin或Heapify之后， Heap必须执行Heapify以Heapify它的部分顺序。 最后有一个O(nlogn)的成本，因为它有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应用了“分而治之”策略，但这是heap.Heapify本身没有算法的事情。

冒泡排序是一种naive算法。

I don't think HeapSort is considered "Divide and Conquer", because in no moment the algorithm sub-divides the problem into sub-problems. To do HeapSort the algorithm Executes ExtractMin or ExtractMax until the Heap is empty. These actions are O(logn) because after each ExtractMin or ExtractMax the Heap has to do Heapify to mantain the partial-order of it. At the end has a cost of O(nlogn) because it does n ExtractMin or ExtractMax.

Here is a pseudo-code

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

Notice that ExtractMin and ExtractMax pops out the minimum or the maximum element of the Heap.

As you can see, i don't see the "Divide and Conquer" strategy.

But the heap.Heapify reorder the elements based on the partial order of the heap. This one defines the relationship between each node and his two child, because of this, heap.Heapify applies a "Divide and Conquer" strategy, but that is a thing of the DataStructre itself no of the algorithm.

And bubble sort is a naive algorithm.