很久很久之前看到过这么一个问题：炉石里一套牌共有 30 张，问至少要探底多少次才能保证可以将牌库排序成想要的顺序？这里给不了解背景的朋友介绍一下，所谓 探底，就是选择牌库底三张牌中的一张将其至于牌库顶。

我们来抽象一下这个题：对于一个大小为 $n$ 的排列 $P$，一次操作可以把前三个数中的一个塞到最后。既然这是个排序算法，我们不妨将其称作 探底排序 好了…… 那么现在问题就是问探底排序的最坏情况下需要多少次操作。我们先研究一个简化版，每次只能把前两个元素中的一个塞到最后。

~~作为一名 TCS 大师，~~我对这个问题挺有兴趣的。但是显然，求出精确解看起来非常难（而且我怀疑甚至不存在通项），于是就退而求其次，分析一下其时间复杂度好了。

我们先来给出一个 $O(n^2)$ 的算法，顺便证明其一定有解。idea 非常简单，我们就模仿选择排序，每次选出剩下的数中最小的一个。具体说来，算法分为 $n$ 轮。第 $k$ 轮过后，我们保证整个序列最后面 $k$ 个元素一定依次是 1 到 $k$，这样 $n$ 轮之后整个数组就有序了。在第 $k$ 轮中，前 $n - k$ 次，我们比较排列前两个数，并且将较大的那个数塞到最后去，这样 $n - k$ 次之后，序列中第一个数一定是 $k$，且接下来 $k - 1$ 个数依次为 $1, \dots, k - 1$，于是我们再把这 $k - 1$ 个数塞到最后，最后把 $k$ 塞到最后即可。伪代码如下：

for k from 1 to n:
    for _ from 1 to n - k: # 选 P[1] ... P[n - k + 1] 中最小的数
        if P[1] > P[2]:
            rotate(1)
        else:
            rotate(2)

    for _ from 1 to k - 1: # 此时 P[1] 一定是 k，将接下来的 1..k-1 塞到最后
        rotate(2)

    rotate(1) # 把 k 塞到最后去

复杂度分析就很简单了，显然是 $O(n^2)$，更确切一点，是刚好 $n^2$。

既然 upper bound 有了，我们再来整一个 lower bound 吧。直觉上应该也是 $\Omega(n^2)$，而且感觉把整个序列倒过来就需要这么多。不妨让我们来打个表试试：

n = 1, worst = 0, reverse = 0
n = 2, worst = 1, reverse = 1
n = 3, worst = 2, reverse = 2
n = 4, worst = 5, reverse = 4
n = 5, worst = 8, reverse = 6
n = 6, worst = 12, reverse = 11
n = 7, worst = 17, reverse = 14
n = 8, worst = 23, reverse = 22
n = 9, worst = 30, reverse = 26
n = 10, worst = 38, reverse = 37

我直接去 OEIS 上搜了一下 worst 这个序列，没找到，但是看着像是一个 $\Omega(n^2)$ 的序列，而且我猜测奇数项和偶数项各自组成一个二次多项式。而且 $n$ 为偶数的情况下，序列翻转几乎就是最坏情况了。接下来我们证明其 lower bound 为 $\Omega(n^2)$。

我们首先给出一个核心观察：

对于任何一个长度为 $k < n$ 的操作序列 $X$，$P$ 的前 $k$ 个数对应的集合和 $PX$ 的后 $k$ 个数对应的集合至多只有一个数不同。

这个观察很好理解： $PX$ 的后 $k$ 个元素只能全部来自于 $P$ 的前 $k+1$ 个元素。这个观察带来的一个推论是，进行恰好 $n$ 次操作后，$PX$ 的前 $\frac{n}{2}$ 个数和 $P$ 的前 $\frac{n}{2}$ 个数至多只有两个数不同（集合意义上）。

有了这个推论，我们就可以开始证明 lower bound 了。对于排列 $P$，假设 $m$ 为最优操作的次数，$X^*$ 为最优操作序列。我们把 $X^*$ 分成若干段，第一段为 $X'$，长度为 $m \bmod n$，之后每段长度为 $n$。由于后面 $m - (m \bmod n)$ 次操作将 $P X'$ 进行排序，我们马上可以得到一个 lower bound：

$$m - (m \bmod n) \geq \frac{n}{2} d(P X'),$$

其中 $d(Q) = |\{i: i \leq \frac{n}{2}, Q_i > \frac{n}{2} \}|$ 表示序列 $Q$ 前一半中有多少个元素排序后不在前一半了。接下来，我们证明存在一个 $P$ ，使得对于任何序列长度不超过 $n$ 的 $X'$ ，都有 $d(P X') = \Omega(n)$，这样就能够整出一个 $\Omega(n^2)$ 的 lower bound。

令 $n = 4k$，我们把 $[n]$ 均匀分成 4 块 $[n] = (A, B, C, D)$，其中 $A = (1, \dots, k)$，$B = (k + 1, \dots, 2k)$，$C = (2k + 1, \dots, 3k)$，$D = (3k + 1, \dots, 4k)$，并令 $P = (A, C, B, D)$ 为一个 $[n]$ 的排列。为了得到了 $d(P X')$ 的一个 lower bound，我们对 $|X'|$ 分类：

• 如果 $|X'| \leq k$，那么 $PX'$ 前一半中至少有 $k - 1$ 个 $C$，故 $d(P X') \geq k - 1$；
• 如果 $k < | X'| \leq 2k$，那么 $PX'$ 后一半中至少有 $k - 1$ 个 $A$，故 $d(P X') \geq k - 1$；
• 如果 $2k < |X'| \leq 3k$，那么 $PX'$ 前一半中至少有 $k - 1$ 个 $D$，故 $d(P X') \geq k - 1$；
• 如果 $3k < |X'| < 4k$，那么 $PX'$ 后一半中至少有 $k - 1$ 个 $B$，故 $d(P X') \geq k - 1$。

这样，我们就代入之前的结果可得：

$$m \geq \frac{n}{2} d (P X') = \frac{n^2}{8} - O(n) = \Omega(n^2).$$

到这里，我们就得到了一个 tight 的 bound，$\Theta(n^2)$。但是还差那么一点点：打表给出的 $n^2$ 的系数为 $\frac{1}{2}$，lower bound 给出的系数是 $\frac{1}{8}$，但是算法给出的 $n^2$ 的系数为 1。我们能否把上下界的常数都改进到 $\frac{1}{2}$ 呢？