堆栈排序及算法分析

堆栈排序

下面介绍 Stack sorting algorithm （堆栈排序），算法的流程如下：
现有如下的数组：

\[ \pi_1 \pi_2 \pi_3 \cdots \pi_n \]

我们构造一个栈，然后进行如下操作：

将 $\pi_1$ 放入栈中；
将 $\pi_2$ 放入栈中：
- 如果 $\pi_2<\pi_1$ ，此时直接入栈；
- 如果 $\pi_2 >\pi_1$ ，此时先让 $\pi_1$ 出栈，再 $\pi_2$ 入栈；
之后所有的流程和上述情况类似，必须要让将要入栈的元素小于栈顶的元素才能入栈，否则就一直弹出元素.
最后，没有元素将要入栈时，将所有栈内的元素依次弹出.

模拟程序代码

下面给出堆栈排序的一个程序模拟代码，基本兼容最新版相关配置.

PythonMATLAB

from itertools import permutations

def if_sorted(t:list) -> bool:
    # 检验是否排列成功
    for i in range(len(t)):
        if i+1 != t[i]:
            return False
    return True


def stack_sorting(t:iter) -> None:
    result = [] 
    stack = []
    for item in t:
        while stack and item >= stack[-1]:
            result.append(stack.pop())
        stack.append(item)

    # 将剩下的元素全部弹出
    while stack:
        result.append(stack.pop())

    return result

if __name__ == '__main__':

    # 对 1~n-1 的数列进行排序
    n = 10

    # permutations 用于生成所有排列
    arrs = permutations(range(1,n))
    max_iters = 0
    for arr in arrs:
        a = stack_sorting(arr)
        iters = 1
        while not if_sorted(a):
            iters += 1
            a = stack_sorting(a)

        max_iters = iters if max_iters < iters else max_iters
        print(f"{arr} 需要的排列次数为 {iters}")

    print(f"最大迭代次数为{max_iters}")

% 提供者：Madeceline
clc;clear;close all;
%%
num=4;
Perm=perms(1:num);
[x,~]=size(Perm);
for i=1:x
    in=Perm(i,:);
    out=stack_code(in);
    disp(['输入：',num2str(in),'，输出：',num2str(out),'是否为单位排列：',num2str(isequal(out,1:num))])
end


function [Output]=stack_code(input)
    stack0=[];Output=[];
    for i=1:length(input)
        passenger=input(i);
        m=find(stack0-passenger<0);
        if isempty(m)
            k=1;
        else
            k=m(end)+1;
        end
        Out=stack0(1:k-1);
        stack0=[passenger,stack0(k:end)];
        Output=[Output,Out];
    end
    Output=[Output,stack0];
end

算法分析与证明

事实上，这个所谓的堆栈排序“算法”并不能给所有的数组都排好序，例如 $231$ ，从左到右：

$2$ 先入栈；
$3$ 要入栈的时候，$2$ 需要出栈；

这就已经出现问题，事实上，我们需要的是小的先出栈，从而达到排序的效果，但是这个例子中排序失败了。

现在我们关心如下两个问题：

什么样的数组（排列）能排序成功？
在刚才的 $231$ 例子中，排序后会变成 $213$ ，此时再进行一次排序就会发现能排序成功为 $123$ . 这是否意味着所有的排列经过有限次堆栈排序都能排序成功？如果是，那么这个“有限次”的上限是多少？

一次排序能成功的条件

在接下来的探讨中，不考虑数组中两个元素相等的情形，并将所有的数组都考虑为 $1,2,\cdots,n$ 的一个排列.

在刚才的例子当中，我们实际上能抽象并推广为如下的排列：

\[ \cdots \pi_{i_1}\cdots \pi_{i_2} \cdots \pi_{i_3}\cdots \]

其中 $i_1<i_2<i_3$ ，我们的发现实际上能归结为如下的结论：

当 $\pi_{i_3}<\pi_{i_1}<\pi_{i_2}$ 时，排序必定不成功.

这个结论是比较显然的，根据大小关系 $\pi_{i_3}$ 必须要比 $\pi_{i_1}$ 要更先弹出到目标数组当中，但是由于 $\pi_{i_2}$ 的存在，$\pi_{i_1}$ 必须弹出，从而导致排序失败.

因此，在有这样的例子之后，这是否是等价条件？我们给出如下的猜想：

猜想：一次排序成功的等价条件

排列：
$$ \pi_1 \pi_2\cdots \pi_n $$
能经过一次堆栈排序后排序成功的充要条件是：$\forall i_1,i_2,i_3 (1\leqslant i_1< i_2 < i_3 \leqslant n)$ ，$\pi_{i_3}<\pi_{i_1}<\pi_{i_2}$ 都不成立.

必要性已经阐述，下面考虑充分性：
在 $n=3$ 的时候，有如下的 $5$ 种排列：

\[ 123,132,213,312,321 \]

这些排列都能排序成功，详细论证略去；

在 $n> 3$ 时，$\pi_{i_1},\pi_{i_2},\pi_{i_3}$ 有 $5$ 种相对位置情形，和上述的 $5$ 种排列类似，我们只需论证：对于任意的 $3$ 个元素，堆栈排序都能保证它们在最终的排序结果中相对位置关系服从大小关系.

例如，对于 $\pi_{i_2}<\pi_{i_1}<\pi_{i_3}$ 的情形，当操作到 $\pi_{i_2}$ 时，有如下两种可能：

此时 $\pi_{i_1}$ 已出栈，这说明 $\exists i (i_1<i<i_2)$ 使得 $\pi_{i_2}<\pi_{i_1}<\pi_i$ ，这就与我们的题设条件矛盾.
因此 $\pi_{i_1}$ 此时必须在栈内，并且 $\pi_{i_2}$ 也必须入栈；
当 $\pi_{i_3}$ 操作时，此时要么 $\pi_{i_1}$ 和 $\pi_{i_2}$ 都已经出栈（相当于三者排序成功），要么全部或一个在栈内，此时 $\pi_{i_3}$ 要入栈时，二者都必须出栈，从而排序成功.

对于其它的四种情形，排序情况都类似，因此猜想证明完毕. $\square$

堆栈排序及算法分析

堆栈排序

模拟程序代码

算法分析与证明

一次排序能成功的条件

评论