排序一副纸牌

Question

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

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

有任何想法吗？

Answer 1

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

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

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

因此，让我们修改Bubblesort，以便进行一些更改以适应扑克牌场景。让我们不要将一副纸牌视为一副纸牌，而是将其更多地视为一个清单。是的，随着修改后的bubbleort的每次迭代，卡组中的第一张卡会不断变化，但是我们可以做到这一点，以便在移动卡的同时仍保持卡组中第一张卡的位置吗？这个问题是解决问题的关键。我的意思是说，将卡移动到卡座的底部不会改变卡的初始顺序，只有交换会改变。例如，考虑以下牌组，其中最左边是顶部，最右边是底部：

注意：（*）表示已标记的卡

*5 3 1 2 6 

在稍后将要说明的算法中，将5移到平台的底部将使平台看起来像这样

3 1 2 6 *5

请注意，现在5在甲板的底部如何，但顺序仍然保留。*符号表示列表/卡组中的第一张卡，因此，如果从左到右从5开始并循环回到3，则将保留顺序。

现在，对于算法，我们如何使用我刚才说的来使Bubblesort的修改版本与原始版本相似？很简单，使用这种标记机制可以使我们实际上不是对牌组进行排序，而是对数字列表进行排序。在开始算法之前，在卡座中标记顶卡。以下是bubbleort每次迭代的其余步骤：

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