sorting - 澄清“如果优先队列使用有序数组实现，则插入排序”，为什么需要“有序”？

Question

插入排序也适用于无序数组，就像这里的示例所示。出于某种奇怪的原因，标题（或此处）中的此语句要求您有一个有序数组来实现插入排序的优先级队列，为什么它有这样的要求？这个维基百科的意思是什么（下面的截图）？

Answer 1

本文介绍了优先级队列用于排序的用法，以及优先级队列的不同实现如何与熟悉的排序算法相对应。

让我们考虑具有操作的 ADT 优先级队列，pop()该操作取出由比较函数定义的“最小”元素push()，并将新元素放入优先级队列中。然后排序可以通过调用push()将未排序数组中的所有元素推入优先队列并调用pop()直到优先队列为空并将弹出的元素放入数组中来完成（好吧，您可以定义一个方法empty()来检查ADT是否为空的）。

伪代码：

unsorted[]
sorted[]
priority_queue q

foreach element in unsorted
    q.push(element)

i = 0
while !q.empty()
    sorted[i] = q.pop()
    i = i + 1

然后我们谈谈如何实现优先级队列。通常，它通过堆有效地实现。但是，不必是堆 - 您可以以效率较低的方式实现它，如维基百科文章中提到的无序数组或有序数组。只要实现满足push()andpop()操作的要求就可以了。

对于无序数组，您可以push()将元素直接放在最后一个元素之后 - 因为它是无序的。当你pop()，由于数组是无序的，你需要搜索整个数组并挑选出最大的元素。（通过将无序数组中的最后一个元素交换到弹出元素的位置，可以轻松完成删除）。它类似于选择排序，因为您本质上是遍历未排序元素的列表（位于优先级队列中）并挑选出最大的元素放入已排序的部分。

可以看到push()这里的操作是在进行插入排序中的插入操作。

对于有序数组，您pop()只需取出第一个元素即可（通过维护起始索引可以轻松完成删除）。但是push()需要您找出放置元素的位置以保持顺序（因为它是有序数组）。这是它与插入排序非常相似的部分，因为您试图将当前元素插入到排序部分（优先级队列实现为有序数组）。

可以看到pop()这里的操作是在做选择排序中的选择操作。