小编典典

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

algorithm

嗨,我在Robert Sedgewick的Algorithms 4th Edition中遇到了一个问题。

出队排序。说明如何对一副纸牌进行排序,限制条件是,唯一允许的操作是查看前两张纸牌的值,交换前两张纸牌以及将顶卡移到纸牌底部。

我真希望有人能够解释如何做到这一点,我真的很迷失。谢谢


阅读 306

收藏
2020-07-28

共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.

希望这可以帮助!

2020-07-28