sorting - 排序问题？

Question

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

此外，冒泡排序适合什么类别（除了可怕的）。

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

Answer 1

我不认为HeapSort被认为是“分而治之”，因为该算法立即将问题细分为子问题。执行 HeapSort 算法ExtractMin或ExtractMax直到 Heap 为空。这些动作是O(logn)因为在每个ExtractMin或必须做ExtractMax的事情之后才能保持它的偏序。最后有一个成本，因为它确实或。HeapHeapifyO(nlogn)n ExtractMinExtractMax

这是一个伪代码

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

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

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

但是heap.Heapify根据堆的部分顺序对元素进行重新排序。这个定义了每个节点和他的两个孩子之间的关系，因此，heap.Heapify应用了“分而治之”的策略，但这是DataStructre本身的事情，不是算法。

冒泡排序是一种naive算法。

Answer 2

如上所述，堆排序绝对不是“分而治之”的算法。堆排序使用堆数据结构来有效地对其元素进行排序。您可以将堆排序视为具有优先级队列的选择排序。

分治算法具有以下特点：

1) 将任务划分为相同任务的较小实例的子任务 2) 递归求解子任务 3) 适当组合结果

如您所见，堆排序不符合这种算法的条件。唯一的相似之处是分治算法的结构反映了二叉树的结构（这通常是堆排序用来实现优先级队列的方法）。

Answer 3

堆排序具有“分而治之”算法（例如快速排序）的时间复杂度，但它的行为不像分而治之算法。

因为它将数据拆分为“排序”部分和“未排序”部分，所以它实际上是一种选择排序。它利用堆数据结构更有效地在每一步从未排序列表中选择最小元素。我想您可以因此说它是“优先队列排序”，但应该提到整个操作可以就地完成，而不是建立一个单独的堆。

堆排序通常优于快速排序，除了快速排序的最坏情况复杂度为O(N^2)（相对于堆排序的最坏情况为O(N.logN)）。

冒泡排序也是一种就地算法，但它被认为是“幼稚的”。