新排序算法——斯大林排序

· · 休闲·娱乐

如何给 n 个数排序？

一个朴素是想法是从头开始，把不符合顺序要求的元素都踢出去，最后就只剩下有序的元素了。但是这称不上一个排序算法，因为这个算法改变了原来的序列，不过我们可以把踢出去的元素记录下来，再递归进行排序，最后 O(n) 把两部分合并起来。

现在我们分析这个算法的复杂度，根据 P1943 中的分析，我们发现每次排序只会选出 O(\log n) 个元素，其他的都会进入到下一轮排序，所以总复杂度高达 O(\frac{n^2}{\log n})，空间复杂度也相当高，喜提 MLE。

考虑如何优化这个算法使它能通过 10^5 的数据。

上面算法中一个显著的问题是每次保留的元素太少了，于是我们采用二分查找优化计算最长不下降子序列，并记录转移点，最后回溯找到最长的序列，把它拿出来，其他的部分递归进行排序，你发现它竟然过了！

分析这个算法的复杂度，由 https://arxiv.org/abs/math/9905032 上的结论得，一个随机序列的最长上升子序列（和最长不下降子序列期望相同）长度期望大约是 2\sqrt n，于是只需要选 O(\sqrt n) 轮就可以把数都选完，每轮需要计算一次最长不下降子序列。总时间复杂度为 O(n\sqrt n\log n)，并且越到后面序列长度越短，所以常数很小，可以通过。

参考实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

mt19937 rnd(random_device{}());

int n;
int a[100001],f[100001],g[100001];

int max_stalin_split(int l){
    int cnt=0;
    f[++cnt]=a[l];
    g[1]=1;
    for (int i=l+1;i<=n;i++){
        if (f[cnt]<=a[i]){
            f[++cnt]=a[i];
            g[i]=cnt;
        }else{
            int j=upper_bound(f+1,f+cnt+1,a[i])-f;
            f[j]=a[i];
            g[i]=j;
        }
    }
    int i=n,j=cnt,idx=0;
    cnt=n;
    for (;i>=l;i--){
        if (j>=0 and g[i]==j){
            a[cnt--]=a[i];
            j--;
        }else f[++idx]=a[i];
    }
    int r=cnt;
    for (int i=idx;i>=1;i--) a[cnt--]=f[i];
    rotate(a+l,a+r+1,a+n+1);
    return n-r+l-1;
}

void stalin_sort_optimized(int l){
    if (l>=n) return;
    shuffle(a+l,a+n+1,rnd); // shuffle 一下，否则遇到一直降序的序列就完了
    int p=max_stalin_split(l);
    stalin_sort_optimized(p+1);
    inplace_merge(a+l,a+p+1,a+n+1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    stalin_sort_optimized(1);
    for (int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}