对一副纸牌进行排序

Question

给定一副 N 张牌。您必须使用以下允许的操作对它们进行排序：

您可以看到前 2 张卡片。
你可以交换它们。
您可以在底部插入顶部。

有什么想法吗？

Answer 1

这似乎是冒泡排序的一个简单案例，这是一种非常低效的排序算法，描述为较小的元素冒泡到顶部（假设您按升序排序）。我将要介绍的修改后的算法与原始的冒泡排序算法非常相似，因此我将首先快速解释一下原始算法。冒泡排序（升序）的工作原理如下，

列表中的第一个元素被标记。
如果标记元素右侧的元素小于标记元素，则交换两个元素。
无论第二步的结果如何，标记向右移动一个位置
重复第二步和第三步，直到标记的元素成为列表中的最后一个元素。只是为了澄清，这意味着当第 3 步导致最后一个元素被标记时，迭代结束并开始新的迭代。

重复上述四个步骤，直到发生迭代，其中标记遍历列表中的每个元素而没有发生单个交换。这是来自维基百科的示例，https://en.wikipedia.org/wiki/Bubble_sort#Step-by-step_example

因此，让我们修改冒泡排序，以便更改一些内容以适应纸牌场景。我们不要将一副纸牌视为一副牌，而更应将其视为一张清单。是的，牌组中的第一张牌会随着我们修改后的冒泡排序的每次迭代而不断变化，但我们能否做到牌在移动的同时仍然保持牌组中第一张牌的位置？这个问题是解决问题的关键。我的意思是，将牌移到牌组底部不会改变牌的初始顺序，只会交换。例如，考虑这副纸牌，其中最左边是顶部，最右边是底部：

注意：(*) 表示标记的卡片

*5 3 1 2 6

在后面要解释的算法中，将5移到牌组的底部会使牌组变成这样

3 1 2 6 *5

注意 5 现在在牌组的底部，但顺序仍然保留。 * 符号表示 list/deck 中的第一张牌，因此如果从左到右读取，从 5 开始循环回到 3，顺序将保留。

现在说到算法，我们如何使用我刚才所说的使这个修改后的冒泡排序版本与原始版本相似？很简单，使用这种标记机制来实现它，这样我们就不会真正对牌组进行排序，而是对数字列表进行排序。在开始算法之前，标记牌组中的顶牌。以下是 bubblesort 每次迭代的其余步骤：

比较上面的卡片和下面的卡片。如果顶牌更大，则与下面的牌交换。如果已标记的牌被交换，则取消标记先前标记的牌并在牌组顶部标记新牌。
将牌组顶部的牌放在底部。
重复第 1 步和第 2 步，直到标记的牌重新浮出水面成为牌组中的第二张牌（顶牌下方的牌）
将顶牌放到牌堆底，使标记的牌成为牌堆顶牌。

算法的每次迭代都会重复这些步骤，直到出现未进行交换的迭代。这是展示修改后的冒泡排序的示例：

注意：(*) 表示标记的卡片

迭代一：

5 3 1 2 6 //Mark the first card in the deck before starting
*5 3 1 2 6 //Compare 5(top card) with 3(card below it)
3 *5 1 2 6 //5 > 3 so swap
*3 5 1 2 6 //Since the marked card (5) was swapped, 3 becomes the new marked 
           //card to preserve original order of the deck
5 1 2 6 *3 //Top card is placed at the bottom
1 5 2 6 *3 //5 > 1 so swap
5 2 6 *3 1 //Put 1 at the bottom
2 5 6 *3 1 //5 > 2 so swap
5 6 *3 1 2 //Put 2 at the bottom
5 6 *3 1 2 //5 < 6 so no swap
6 *3 1 2 5 //Put 5 at the bottom
*3 1 2 5 6 //Marked card is second to top card, so put 6 at the bottom
           //Marked card is now at the top, so new iteration begins

在进入第二次迭代之前，我想指出，如果您运行原始的冒泡排序，则一次迭代的结果序列将与我们修改后的算法一次迭代的结果序列相同.

迭代二：

*3 1 2 5 6 //3 > 1, so swap
*1 3 2 5 6 //Remark accordingly since the former marked card was swapped
3 2 5 6 *1 //Place 1 at the bottom
2 3 5 6 *1 //3 > 2, so swap
3 5 6 *1 2 //Place 2 at the bottom
3 5 6 *1 2 //3 < 5 so no swap
5 6 *1 2 3 //Place 3 at the bottom
5 6 *1 2 3 //5 < 6 so no swap
6 *1 2 3 5 //Place 5 at the bottom.
*1 2 3 5 6 //Since marked card is second to top card, place 6 at the bottom and end iteration

迭代三：

*1 2 3 5 6 //1 < 2 so no swap
2 3 5 6 *1 //Place 1 at the bottom
3 5 6 *1 2 //2 < 3 so no swap and place 2 at the bottom
5 6 *1 2 3 //3 < 5 so no swap and place 3 at the bottom
6 *1 2 3 5 //5 < 6 so no swap and place 5 at the bottom
*1 2 3 5 6 //Since marked card is second to top card, place 6 at the bottom and end iteration.

我们现在知道要结束算法，因为整个迭代已经发生，没有发生任何交换，所以现在对牌组进行了排序。至于运行时间，就交换而言，最坏的情况发生在最大迭代次数为 n（甲板的大小）次时。并且对于每一次迭代，最坏情况下发生的交换次数也是n次。所以大O是n*n或O(n^2).

对一副纸牌进行排序

Sort a deck of cards

sorting

algorithm

playing-cards

data-structures