整理一副牌

Question

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

1. 你可以看到前2张牌。
2. 你可以交换。
3. 可以在底部插入顶部。

任何想法?

Answer 1

这似乎是冒泡排序的一个简单例子，这是一种非常低效的排序算法，由较小的元素冒泡到顶部来描述(假设您按升序排序)。我将要展示的修改后的算法与最初的冒泡排序算法非常相似，所以我将首先快速解释一下最初的算法。冒泡排序(升序排序)的工作方式如下:

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

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

那么让我们修改一下bubblesort，使一些东西改变以适应deck of cards的场景。我们不要把这副牌看成是一副牌，而是看成一个列表。是的，牌组中的第一张牌会随着我们修改的泡泡排序的每次迭代而不断改变，但我们能否做到在保持牌组中第一张牌的位置的同时保持牌组中的第一张牌的位置?这个问题是解决这个问题的关键。我想说的是，将牌移到牌的底部不会改变牌的初始顺序，只有交换才会改变。例如，考虑这副牌，最左边是顶部，最右边是底部:

注:(*)表示已标记卡片

*5 3 1 2 6 

在后面将解释的算法中，将5移到牌堆的底部将使牌堆看起来像这样

3 1 2 6 *5

注意5现在是如何在甲板的底部，但顺序仍然保持不变。*符号表示列表/牌组中的第一张牌，所以如果从左到右读取，从5开始循环到3，顺序保持不变。

现在说到算法，我们如何使用我刚刚说的使这个修改版本的冒泡排序与原始版本相似?很简单，使用这个标记机制，这样我们就不是在对一个牌进行排序，而是在对一个数字列表进行排序。在开始演算法之前，先在牌堆的最上面画上记号。以下是每次迭代bubblessort的其余步骤:

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.

我们现在知道该结束算法了，因为整个迭代过程中没有发生任何交换，所以deck现在已经排序好了。至于运行时，就交换而言，最坏的情况发生在迭代次数最多的时候，即n(牌组大小)次。对于每次迭代，最坏情况下的交换次数，也是n次。所以大O是n*n或O(n²)