【算法】在有限制的情况下将一副牌排序（类似冒泡排序）

Table of Contents

算法题目
#

最近发现自己之前在知乎提问过一个算法问题，这个问题是 10 年前在我面试腾讯微信 NLP 组实习岗位时被问到的。

如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。

由于当时是我第一次实习面试，有点紧张，而且我当时没有问清楚，隐含条件是其实还能知道这副牌的总数，所以没有做出来。

看了下知乎的答案，没有让我特别满意的，所以时隔 10 年决定自己来回答这个算法题。

题目分析
#

抽象一下题目，其实就给一个数组，这个数组只有以下几个接口：

返回数组元素个数
返回数组第一个元素
返回数组第二个元素
交换数组第一个和第二个元素
将数组第一个元素到到数组最后

将数组排序。

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class SortDeckOfCards {
    private final List<Integer> cards;

    public SortDeckOfCards(List<Integer> cards) {
        this.cards = cards;
    }

    public List<Integer> sort() {
        // Implement This Function
        // Only with private functions in this class
    }

    private int getNumberOfCards() {
        return cards.size();
    }

    private void swapFirstTwoCards() {
        Collections.swap(cards, 0, 1);
    }

    private void putFirstCardToEnd() {
        int value = cards.remove(0);
        cards.add(value);
    }

    private int getFirstCard() {
        return cards.get(0);
    }

    private int getSecondCard() {
        return cards.get(1);
    }
}

这个算法问题其实和冒泡排序很相似，冒泡排序的思路是对于长度为 n 的数组，进行 n 次循环，第 i 次循环找到整个数组第 i 小的值，即数组 index [ i - 1, n) 最小的值，然后放在数组第 i 个位置（冒泡🫧），每次循环后数组 index [0, i) 都是有序的。

我们可以通过一个实例来看这个算法问题应该怎么解决。

假设起始数组为[1, 4，5, 2, 3]一共5个数字

【操作 a】首先比较前两个数，如果第 1 个数小于第 2 个数，将前两个数对调，否则保持原顺序。最后将第 1 个数的放在数组最后。（类似冒泡排序每次循环的比较)

我们重复【操作 a】一共 4 次依次得到

[1, 5, 2, 3, 4]

[1, 2, 3, 4, 5]

[1, 3, 4, 5, 2]

[1, 4, 5, 2, 3]

因为总共 5 个数字，而现在第 1 个数字比其他 4 个数字都小，所以是最小的的数字。

【操作 b】对调前两个数，然后把第一个数放最后

【操作 c】把第一个数放最后

然后我们进行【操作 c】把第 1 个数字放在最后得到（类似冒泡排序的冒泡操作）

[4, 5, 2, 3, 1]

我们可以保证最后 1 个数字是有序的。然后我们重复【操作 a】但这次只重复 3 次依次得到

[4, 2, 3, 1, 5]

[2, 3, 1, 5, 4]

[2, 1, 5, 4, 3]

因为现在第 1 个数字已经和除了最小的数字都比较了，所以是整个数组第 2 小的数。而很巧的是现在第 2 个数就是之前最小的数。所以我们连续进行 1 次【操作 b】和 1 次【操作 c】则得到

[5, 4, 3, 1, 2]

这时最后 2 个数字是有序的，接着我们重复【操作 a】但这次只重复 2 次依次得到

[4, 3, 1, 2, 5]

[3, 1, 2, 5, 4]

因为现在第 1 个数字已经和除了最小的和第 2 小的数字都比较了，所以是整个数组第 3 小的数。而很巧的是现在后面 2 个数就是之前找到的最小的和第二小的。所以我们连续进行 2 次【操作 b】和 1 次【操作 c】则得到

[5, 4, 1, 2, 3]

这时最后 3 个数字是有序的，然后我们重复【操作 a】但这次只重复 1 次依次得到

[4, 1, 2, 3, 5]

因为现在第 1 个数字已经和除了最小的，第 2 小的数字和第 3 小的数字都比较了，所以是整个数组第 4 小的数。而很巧的是现在后面 3 个数就是之前找到的最小的，第 2 小的和第 3 小的。所以我们连续进行 3 次【操作 b】和 1 次【操作 c】则得到

[5, 1, 2, 3, 4]

这时最后 3 个数字是有序的，第一个数字就是最小的了，然后连续进行 4 次【操作 b】和 1 次【操作 c】则得到有序的数组。

这其实就是这个算法的解法，如果抽象成伪代码

【操作a】首先比较前两个数，如果第1个数小于第2个数，将前两个数对调，否则保持原顺序。
【操作b】将第1个数字放在最后
function sortDeckOfCards(cards):
    n = getNumberOfCards(cards)
    for i from 0 to n-1:
        // 执行操作a，找到第i小的数
        for j from 0 to n-i-1:
            if cards[0] < cards[1]:
                swapFirstTwoCards(cards)
            putFirstCardToEnd(cards)
        
        // 执行操作b，将第i小的数放到最后
        for k from 0 to i-1:
            swapFirstTwoCards(cards)
            putFirstCardToEnd(cards)
        putFirstCardToEnd(cards) 
    return cards

算法复杂度
#

时间复杂度分析
#

外层循环：
- 运行 n 次，每次找到第 i 小的元素并将其移到正确位置。
内层第一个循环 (操作 a):
- 第一次外层循环运行 n-1 次。
- 第二次外层循环运行 n-2 次。
- 依次类推，最后一次外层循环运行 1 次。
- 这部分的总操作次数是：
- $\sum_{i=1}^{n-1} (n-i) = (n-1) + (n-2) + \ldots + 1 = \frac{(n-1)n}{2} = O(n^2)$
内层第二个循环 (操作 b):
- 第一次外层循环不运行（即 0 次）。
- 第二次外层循环运行 1 次。
- 依次类推，最后一次外层循环运行 n-1 次。
- 这部分的总操作次数是：
- $\sum_{i=0}^{n-1} i = 0 + 1 + 2 + \ldots + (n-1) = \frac{(n-1)n}{2} = O(n^2)$

综上所述，总时间复杂度为： $O(n^2) + O(n^2) = O(n^2)$

空间复杂度分析
#

原地排序，不需要额外的空间来存储数据。所以空间复杂度是 $O(1)$

算法代码
#

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class SortDeckOfCards {
    private final List<Integer> cards;

    public SortDeckOfCards(List<Integer> cards) {
        this.cards = cards;
    }

    public List<Integer> sort() {
        int n = getNumberOfCards();
        // corner case
        if (n <= 1) {
            return cards;
        }
        // get the i-th smallest card
        // after one loop, cards index [n-1-i, n-1] is sorted
        for (int i = 0; i < n; i++) {
            // Because cards index [n-1-(i-1), n-1] is already sorted
            // so just need to get smallest in [0, n-1-i)
            // eg. if total card is 3 and want to get the smallest card, just need to compare 2 times
            for (int j = 0; j < n - i - 1; j++) {
                int first = getFirstCard();
                int second = getSecondCard();
                if (first < second) {
                    swapFirstTwoCards();
                }
                putFirstCardToEnd();
                System.out.println(cards);
            }
            // index 0 is the i-th smallest card
            // index 1 to i-1 is the ordered 0 to i-1 the smallest card
            // put [1, i-1]th to the end
            for (int k = 0; k < i; k++) {
                swapFirstTwoCards();
                putFirstCardToEnd();
            }
            // put i-th smallest card to teh end
            putFirstCardToEnd();
        }
        return cards;
    }

    private int getNumberOfCards() {
        return cards.size();
    }

    private void swapFirstTwoCards() {
        Collections.swap(cards, 0, 1);
    }

    private void putFirstCardToEnd() {
        int value = cards.remove(0);
        cards.add(value);
    }

    private int getFirstCard() {
        return cards.get(0);
    }

    private int getSecondCard() {
        return cards.get(1);
    }

    public static void main(String[] args) {
        List<Integer> cards = new LinkedList<>(List.of(1, 4, 5, 2, 3));
        SortDeckOfCards sortDeckOfCards = new SortDeckOfCards(cards);
        System.out.println(sortDeckOfCards.sort());

        cards = new LinkedList<>(List.of(5, 4, 3, 2, 1));
        sortDeckOfCards = new SortDeckOfCards(cards);
        System.out.println(sortDeckOfCards.sort());

        cards = new LinkedList<>(List.of(6, 6, 2, 5, 7));
        sortDeckOfCards = new SortDeckOfCards(cards);
        System.out.println(sortDeckOfCards.sort());
    }
}

算法题目 #

题目分析 #

算法复杂度 #

时间复杂度分析 #

空间复杂度分析 #

算法代码 #