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

Question

您好，我在 Robert Sedgewick 的算法第 4 版中遇到了一个问题。

Dequeue sort. Explain how you would sort a deck of cards, with the restriction that the only allowed operations are to look at the values of the top two cards, to exchange the top two cards, and to move the top card to the bottom of the deck.

我希望有人能解释这是如何完成的，我真的迷路了。谢谢你

Answer 1

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

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

在伪代码中，这看起来如下:

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.

希望这对您有所帮助!