新的排序算法——栈排序

· · 算法·理论

前言

栈排序最初于2024年某日由作者独自完成，后学习知识，分析算法，成此文章。

2020/12/15第一稿

2020/12/20修改部分内容

简要说明一下，本算法没有太好的时空复杂度，但有微乎其微的优点

算法流程

  1. 建立3个栈（本文使用手写栈）a,b,c，a为"杂栈"，b为"单调栈"，c为总栈(原数组)，初始数组元素全在栈c中。
  2. 遍历c栈顶，若b栈为空或栈顶元素小于c栈顶，则将c栈顶元素移至b栈顶，否则移至a栈顶。
  3. 此时若栈a为空，退出循环，由底至顶输出栈b即为答案。
  4. 否则将栈b,栈a由顶至底移回栈c\ \ 压行代码如下(移动了第3步和第4步的位置) 
    void stack_sort(int* l,int* r){          // [l,r)
int a[r-l],b[r-l],*c=l;              //初始化
int la=0,lb=0,lc=r-l;
while(la || !lb){                    //第三步，注意防止初始化完直接退出
    while(lb)c[lc++]=b[--lb];        //第四步
    while(la)c[lc++]=a[--la];
    while(lc){                       //第一步
        if(!lb || c[lc-1]>=b[lb-1])b[lb++]=c[--lc];
        else a[la++]=c[--lc];
    }
}
for(int i=0;i<lb;i++)*(l+i)=b[i];    //第三步
}

算法原理

设在上一轮操作最后，栈c中上一轮栈b的最后一项下标为x，则这一轮操作开始时的栈c可分为上一轮的栈b的区间[1,x]和上一轮的栈a的区间(x,c.len]\ 用栈不太好理解，其实这里仔细看看，可以将算法的部分简化为不断寻找栈c中的单调序列（B），并使得下一次的寻找以栈a本轮的区间开始\ \ 假设本轮开始时的栈c的[1,x]一定是单调且与已排序序列的部分是相同的。\ \ 分配完完栈a上一轮的区间，b栈顶的元素一定变成了栈a上一轮的区间中的最大值，再进入栈b的区间，又因为刚才的假设，以此可以推出：\ \ 回来看看假设，同样一直反推，最后推到刚初始化完毕，这是栈b为空，就肯定满足假设了。\ \ 这不就是选择排序的变种嘛

算法分析

空间复杂度：没什么好说的，O(n)\ 稳定，因为

if(!lb || c[lc-1]>=b[lb-1])

最低时间复杂度：O(n)\ 最高时间复杂度：O(n^2)\ 期望时间复杂度：O(n^2)\ \ 附上部分排序算法的相同样例花费时间

冒泡排序  O(n^2):
 3320ms

选择排序  O(n^2):
 1031ms

快速排序  O(n log n):
 1ms

栈排序 O(n^2):
 3203ms

可以看出，时间不如选择排序\ 该算法理论时间比选择排序略优，只是常数较大，约是选择排序的6倍

鸣谢

鸣谢TH911,为算法的分析做出贡献。\ 鸣谢选择排序发明者，提供算法最初的灵感。