使用有限的操作对双端队列进行排序？

Question

嗨,我在Robert Sedgewick的Algorithms第4版中遇到了一个问题.

出队排序.解释你如何对一副牌进行排序,限制是唯一允许的操作是查看前两张牌的值,交换前两张牌,以及将顶牌移动到牌组的底部.

我希望有人可以解释如何做到这一点,我真的迷失了.谢谢

Answer 1

与其想象一副牌有顶部和底部，不如想象一副牌排列成一个环。您可以想象在两张特定卡之间放置一个标记，然后对应于牌组的顶部。你的“交换最上面的两张牌”的操作就是将两张牌交换到标记的左侧，而“将一副牌的顶部移到底部”的操作则对应于将标记向左移动一步。

鉴于此，您可以自然地调整冒泡排序以在此设置中工作。将环中的位置之一永久标记为起点。然后，重复执行以下操作：如果标记左侧的两张卡乱序，则交换它们。然后，将标记向左移动一步。作为规则的一个例外，如果标记比标记的初始位置早一步，则不要进行比较。如果你绕圈子不交换任何东西，你就完成了！

在伪代码中，这将如下所示：

repeat the following until no swaps are made:
    counting from i = 1 to n - 1, inclusive:
       if the top two cards are out of order, swap them.
       move the top card of the deck to the bottom.
    then, move the top card of the deck to the bottom.

希望这可以帮助！