对一副纸牌进行排序

Question

给定一副由 N 张牌组成的卡牌，你需要使用以下可行操作进行排序：

1. 你可以看到顶部的两张牌。
2. 你可以交换它们。
3. 你可以将顶部的牌插入到底部。

有什么想法吗？

- abhishekgarg

---

@RickS - 如果我可以补充一下：你有什么想法？你尝试过什么？ - shapiro yaacov

我的猜测是：选择顶部两个数中更大的那一个，然后将其推到底部。重复这个过程。这应当使用 O(n^n) 或者类似这样可怕的时间复杂度完成... - shapiro yaacov

我尝试了以下方法。首先查看前两个数字，将较大的元素放在顶部，然后将其插入到底部。重复进行n次操作。 - abhishekgarg

最简单的答案就是将其实现为冒泡排序的修改版。 - RBarryYoung

如果您觉得这个答案有帮助，请不要忘记将其标记为已接受。我希望它能提供一些见解。 - Chris Gong

Answer 1

这似乎是一个简单的冒泡排序案例，它是一种非常低效的排序算法，其中较小的元素向上冒泡（假设您正在按升序排序）。我即将介绍的修改后算法与原始冒泡排序算法非常相似，因此我将快速解释原始算法。冒泡排序（按升序）的工作方式如下：

1. 标记列表中的第一个元素。
2. 如果标记元素右侧的元素小于标记元素，则交换这两个元素。
3. 无论步骤二的结果如何，标记都向右移动一格。
4. 重复步骤2和步骤3，直到标记元素成为列表中的最后一个元素。仅供澄清，这意味着当步骤3导致标记为最后一个元素时，迭代结束并开始新迭代。

以上四个步骤会一直重复，直到发生一个迭代，标记遍历整个列表而没有进行一次交换。以下是来自维基百科的示例：https://en.wikipedia.org/wiki/Bubble_sort#Step-by-step_example

现在让我们修改冒泡排序使其适应卡牌场景。我们不要把卡牌当作一副牌，而是看作一个列表。是的，随着我们修改后的冒泡排序的每次迭代，牌堆中的第一张牌将不断变化，但我们可以使得卡牌在保持牌堆顶部第一张牌的位置的同时进行移动吗？这个问题是解决问题的关键。我的意思是说，将卡牌移到牌堆底部不会改变卡牌的初始顺序，只有交换才会改变顺序。例如，考虑以下卡牌组合，其中最左侧是顶部，最右侧是底部：

注意：(*)表示标记牌。

*5 3 1 2 6 

在接下来将要解释的算法中，将5移动到牌堆底部会使得牌堆看起来像这样。

3 1 2 6 *5

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

现在来看算法，我们如何利用我刚才所说的内容使这个修改后的冒泡排序与原始版本相似呢？简单，使用这个标记机制，使我们不是真正地对一个牌堆进行排序，而是对一组数字进行排序。在开始算法之前，标记牌堆顶部的牌。以下是每次冒泡排序迭代的其余步骤：

1. 将顶部牌与下面的牌进行比较。如果顶部牌更大，则与下面的牌交换。如果交换了标记牌，则取消标记先前标记的牌并标记牌堆顶部的新牌。 2. 将牌堆的顶部牌放到底部。 3. 重复执行步骤1和步骤2，直到标记的牌重新出现在牌堆中成为第二张牌（顶部牌下方的牌）。 4. 将顶部牌放到牌堆底部，将标记牌作为牌堆的顶部牌。

这些步骤会在每次算法迭代中重复执行，直到发生没有进行任何交换的迭代为止。以下是一个示例，展示了修改后的冒泡排序：

注意：(*)表示标记牌

第一次迭代：

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）。

- Chris Gong

---

我们可不可以不标记卡片，而是直接循环遍历卡片呢？所以在你的情况下，它将从0到4进行循环，并一直循环到没有交换为止。 - Serge

@Serge 你好，很抱歉回复晚了。这个算法基于冒泡排序，所以才会标记卡片。关于“遍历卡片”的意思我不太确定，你能提供一个例子吗？ - Chris Gong