用最少的步数对一副牌进行排序

Question

我们有n张卡片，每张卡片编号从1到n。所有卡片都是随机洗牌的。我们只允许执行MoveCard(n)操作，它将编号为n的卡片移动到牌堆顶部。我们需要用最少的MoveCard操作对牌堆进行排序。我能想到的朴素方法是从MoveCard(n)，MoveCard(n-1)，MoveCard(n-2).... MoveCard(1)开始。这种方法将在n次MoveCard操作中解决问题。但是我们能不能进行优化呢？例如，如果输入是：3 1 4 2，按照我的方法：

                4 3 1 2

                3 4 1 2

                2 3 4 1

                1 2 3 4

MoveCard操作是4次。

但我们可以用最少的移动次数来解决这个问题：

优化后的解决方案是：

                3 1 4 2

                2 3 1 4

                1 2 3 4

MoveCard操作次数为2。

从上面优化的解决方案中，我认为以下方法可以解决问题。

我们总是选择要移动的元素，该元素将排序后的元素置于顶部和底部，并满足排序子数组从开头到最大元素应小于从底部到最小元素的排序子数组。

在这种情况下：

         3 1 4 2

将2移到第二个位置，得到2 3 1 4 {其中2和3从最开始就已经排好序，而4是从底部排好序的}

现在我们选择1，就可以得到完全排序过的数组。1 2 3 4。

- sunmoon

---

看起来这是一个问题，需要在http://cs.stackexchange.com/上提问。 - Leo

应该将其转移到 CS StackExchange。 - Tomasz Kowalczyk

不知道为什么人们要踩这个。看起来是一个很好的编程练习。 - Aseem Goyal

@luk32：我的意思是与在线评测程序有关的东西 :) - Aseem Goyal

算法是编程的重要组成部分。如果设计算法不是编程，那么我们很容易教计算机为我们完成所有编程，因为这意味着编程只是将算法翻译为代码。因此，我说：重新开放。 - Jasper

Answer 1

一个简单的方法是逆序查看数字。如果前两个数字不按顺序排列，则移动较低的数字。如果它们按顺序排列，则查找下一个更小的数字。在找到一个未按顺序排列的数字后，移动该数字，然后将其下方的每张牌按降序排列。

基本上，找到n。如果n-1在数组中位于n之后，则将n-1移动到开头。n--，然后重复。

例如：

2 4 3 1    // 3 comes after 4, so move 3
3 2 4 1    // move 2
2 3 4 1    // move 1
1 2 3 4    // done after 3 moves

3 1 4 2    // 3 comes -before- 4, so leave it alone. 2 comes after 3, move it
2 3 1 4    // move 1
1 2 3 4    // done after 2 moves

它最终与天真的方法相同，但仅从“最佳”起点开始。您不总是需要移动顶部卡片。

最坏情况时间复杂度为O(n^2)，因为您必须对每个数字进行无序搜索。我不能证明这是可能的最佳复杂度，但这肯定是最简单和最清晰的方法。

最坏情况下的移动次数是n-1，因为您始终可以将n卡留在原处。

现在，如果您只想知道需要多少次移动，而不是实际排序，您可以在第一次移动时停止。例如，如果您必须移动3，因为它在4之后，则需要3次移动。您可以看到，如果3位于前面，则您始终必须将其下面的每张卡片移动到前面。

- Geobits