您好,我在 Robert Sedgewick 的《算法第四版》中遇到了一个问题。
出队排序。解释如何对一副牌进行排序,但唯一允许的操作是查看最上面两张牌的值、交换最上面两张牌以及将最上面的牌移动到这副牌的底部。
我希望有人能解释一下这是如何完成的,我真的迷失了。感谢您
不要认为这副牌有顶部和底部,而是想象这副牌排列成一个环。您可以想象在两张特定的卡片之间放置一个标记,然后该标记对应于这副牌的顶部。你的“交换上面两张牌”的操作就是将两张牌交换到标记左边,而“将牌堆顶部移到底部”的操作则相当于将标记向左移动一步。
鉴于此,您自然可以调整冒泡排序以在此设置中工作。将环中的一个位置永久标记为起点。然后,重复执行以下操作:如果标记左侧的两张牌顺序不正确,则交换它们。然后,将标记向左移动一步。作为该规则的一个例外,如果标记比标记的初始位置早一步,则不进行比较。如果你绕了一圈而不交换任何东西,你就完成了!
在伪代码中,这将如下所示:
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.
希望这可以帮助!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)