排序算法：堆栈排序 (Stack-Sorting)

堆栈排序是指利用一个后进先出的堆栈结构，按照特定规则对排列进行重新排列的过程。

1. 算法规则与定义

给定一个排列 $\pi = \pi_1 \pi_2 \cdots \pi_n \in S_n$，通过堆栈 $stack$ 操作得到输出排列 $S(\pi)$。

操作步骤

• Step 1: $\pi_1$ 入栈。
• Step 2: 依次处理后续元素 $\pi_i$：
  1. 若 $\pi_i < M$（$M$ 为当前栈顶元素），将 $\pi_i$ 入栈。
  2. 若 $\pi_i > M$，则将 $M$ 出栈并加入输出序列。
  3. 重复第 2 步，直到 $\pi_i$ 能够入栈。
• 最终状态: 待所有输入处理完后，将栈内剩余元素依次弹出。
• 结果: 得到最终的出栈排列 $S(\pi) = \sigma_1 \sigma_2 \cdots \sigma_n$。

2. 示例

例： 设 $\pi = 3142$

1. $3$ 入栈。
2. $1 < 3$，则 $1$ 入栈（栈内：$3, 1$）。
3. 处理 $4$：因 $4 > 1$，弹出 $1$；因 $4 > 3$，弹出 $3$；随后 $4$ 入栈（输出序列目前为：$1, 3$）。
4. $2 < 4$，则 $2$ 入栈（栈内：$4, 2$）。
5. 扫描结束，依次弹出 $2, 4$。 最终得到：$S(3142) = 1342$。

3. 核心引理：递归分解

将排列 $\pi$ 分解为： \(\pi = \pi_L \cdot n \cdot \pi_R\) 其中 $n$ 是排列中的最大元素，$\pi_L$ 是 $n$ 左侧的部分，$\pi_R$ 是 $n$ 右侧的部分。

引理内容： \(S(\pi) = S(\pi_L) \cdot S(\pi_R) \cdot n\)

4. 定理：堆栈可排序性与 231-模式

定理： 对于 $\pi \in S_n$，使得 $S(\pi) = id$（即 $1, 2, \dots, n$）的充分必要条件是 $\pi$ 不包含 231-pattern。

231-pattern: 指存在下标 $i < j < k$，使得其对应数值的大小顺序为 $\pi_k < \pi_i < \pi_j$。

证明

① 必要性 ($\implies$)

若 $S(\pi) = id$，则 $\pi$ 不包含 231-pattern。 反证法：若 $\pi$ 包含 231-pattern，根据引理 $\pi = \pi_L \cdot n \cdot \pi_R$：

• 若 $\pi_L$ 中包含较大的数，而 $\pi_R$ 中包含较小的数，则在输出序列 $S(\pi) = S(\pi_L)S(\pi_R)n$ 中，较小的数会排在较大的数后面，导致 $S(\pi) \neq id$。

② 充分性 ($\impliedby$)

若 $\pi$ 不包含 231-pattern，则 $S(\pi) = id$。

• 使用数学归纳法 (Induction)：
  • $n=2$ 时：$S(12)=12$，$S(21)=12$，均符合。
  • 假设对 $n-1$ 阶排列成立。
  • 对于 $n$ 阶排列 $\pi = \pi_L \cdot n \cdot \pi_R$：
    • 若 $\pi$ 不含 231-pattern，则 $\pi_L$ 中的所有元素均小于 $\pi_R$ 中的元素。
    • 即 $\pi_L = {1, \dots, i-1}$ 且 $\pi_R = {i, \dots, n-1}$。
    • 根据归纳假设，$S(\pi_L)$ 和 $S(\pi_R)$ 均递增，代入引理得 $S(\pi) = id$。

5. Outline