洛谷【P1177】【模板】基数排序

题目传送门：https://www.luogu.org/problemnew/show/P1177

我对计数排序的理解：https://www.cnblogs.com/AKMer/p/9649032.html

所谓基数排序，我们可以简单的理解成是多关键字的计数排序。

假设我们要排序一些数据，把这些数据按照第一关键字\(>\)第二关键字\(>...>\)第\(n\)关键字的优先级排序。

那么我们只需要按第\(n\)关键字，第\(n-1\)关键字...第\(1\)关键字倒着做计数排序就行了。我们做怎么样的计数排序呢？

假设\(k+1\)到\(n\)号关键字已经做完了，我们来做第\(k\)个。由于之前的关键字已经全部从小到大排好了，那么我们在将第\(k\)个关键字做计数排序的时候只需要倒着枚举就可以了，假设某两个数据第\(k\)个关键字是相同的，那么显然是\(id\)越靠后的数据越大，这与计数排序的\(sum[a[i]]--\)有着十分好的契合度。至于第\(k\)个关键字不同的，自然也就会区分开来。

时间复杂度：\(O(n*关键字个数)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

int n;

int sum[10],id[maxn],rk[maxn];//id[i]表示第k+1到n号关键字排好后第i个数据的原本编号，rk[i]表示原本编号为i的数据在进行完k号关键字的计数排序后的排名

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct num {

    int v[11];

    void print() {

        int pos=1;

        while(pos<=10&&!v[pos])pos++;//忽略前导零

        for(int i=pos;i<=10;i++)

            printf("%d",v[i]);

        printf(" ");

    }

}a[maxn];

int main() {

    n=read();

    for(int i=1;i<=n;i++) {

        int x=read();

        for(int j=10;j;j--)

            a[i].v[j]=x%10,x/=10;

        id[i]=i;//把整数拆成10个关键字排序，每个关键字的值域都是[0,9]

    }int *x=id,*y=rk;//因为到时候要交换数组，用指针就是O(1)的了。

    for(int key=10;key;key--) {//倒着做计数排序

        memset(sum,0,sizeof(sum));

        for(int i=1;i<=n;i++)sum[a[i].v[key]]++;

        for(int i=1;i<=9;i++)sum[i]+=sum[i-1];

        for(int i=n;i;i--)y[sum[a[x[i]].v[key]]--]=x[i];//y[i]记录排名第i的数据，记住不要把a[x[i]]写成a[i]了，x是之前全部排好后的顺序

        for(int i=1;i<=n;i++)x[y[i]]=i;//x[i]记录第i个数据的排名

        swap(x,y);//交换，不然做下一次id和rk的意思就反了，那么就会错

    }for(int i=1;i<=n;i++)

         a[x[i]].print();//输出

    return 0;

}

巴特西

洛谷【P1177】【模板】基数排序

最新文章

热门文章