分块排序

_recollector_ · 2024-11-02 17:33:04 · 个人记录

前置芝士：分块，堆，排序

• 这是一种 O(n \log \sqrt{n}) 的神奇排序。

我们先对数列分块，对每一块排序，然后合并就可以了。

合并的复杂度可以用堆做到 O(n\log \sqrt{n})

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5,B=1e4+5;
int a[N],L[B],R[B],now[B];
vector<int>block[B],ans;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int t=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=t;++i)
    {
        L[i]=R[i-1]+1;
        R[i]=R[i-1]+t;
    }
    if(R[t]<n)
    {
        ++t;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;++i)
    {
        for(int j=L[i];j<=R[i];++j)
            block[i].push_back(a[j]);
        sort(block[i].begin(),block[i].end());
    }
    for(int i=1;i<=t;++i)
        q.emplace(block[i][0],i);
    while(!q.empty())
    {
        int x=q.top().first,y=q.top().second;
        q.pop();
        ++now[y];
        ans.emplace_back(x);
        if(now[y]<block[y].size())q.emplace(block[y][now[y]],y);
    }
    for(auto &x:ans)
        cout<<x<<' ';
}