P1177 【模板】排序 题解

· · 题解

基数排序

思路

我们在比较两个数的大小时，是找到第一位不同的数的位置后比较大小。

考虑将每个数按个位，十位，百位...进行比较，确保在比较第 i 位时所有数已经按前 i-1 位排好序，也就是说我们要知道 n 个数只看前 i-1 位数排序后的位置。

若第 a_j 的第 i 位比 a_z 的第 i 位小，那么在只看前 i 位数的情况下一定是 a_j < a_z，注意此时的小于符号是我们定义的。

若第 a_j 的第 i 位等于 a_z 的第 i 位，那么保持原来的位置关系就行了。

这里引用 OI wiki 的图供读者理解：

实现

记 sum_j 表示第 i 位上的值 \le j 的数有几个，o=10，只考虑第 1 位获取排名方式如下：


    for(int i = 1;i <= n;i++) sum[a[i]%o]++;//值为a[i]%o的个数有几个 
    for(int i = 1;i <= 9;i++) sum[i] += sum[i-1];//前缀 
    for(int i = n;i >= 1;i--) id[sum[a[i]%o]--] = i,a[i]/=o;//计算排名

假设一个数第一位为 i，那么他的排名至少是小于 i 的个数，相同的话就累加一下，那么 sum_i 的初值就是值为 i 的排名最靠后的位置，由于这里是算的第一位的，我们直接默认顺序为输入顺序，于是直接从后往前依次给排名，给完后 sum_{a[i] \mod o}-1 是因为最后一个排名算完了，前一个的位置就是当前的位置 -1。

若不是第一位，只需要改一部分即可，实现是差不多的。


      for(int i = 0;i <= 9;i++) sum[i] = 0;
        for(int i = 1;i <= n;i++) id1[i] = id[i];//新的位置
        for(int i = 1;i <= n;i++) sum[a[i]%o]++;
        for(int i = 1;i <= 9;i++) sum[i] += sum[i-1];
        for(int i = n;i >= 1;i--) id[sum[a[id1[i]]%o]--] = id1[i],a[id1[i]]/=o;

可以发现唯一的区别就是 i 变为了 id1_i，这是因为数的顺序改变了，我们初始是默认第 i 个数的排名是 i。

可以发现时间复杂度是 O\left ( n \log_{10}{V} \right ) ，空间复杂度 O\left ( n \right ) 。

然后就没有了。

code

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    template<typename T>
    void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
    template<typename T,typename... Args>
    void read(T &_x,Args&...others){Read(_x);Read(others...);}
    const int BUF=20000000;char buf[BUF],top,stk[32];int plen;
    #define pc(x) buf[plen++]=x
    #define flush(); fwrite(buf,1,plen,stdout),plen=0;
    template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++top]=48+x%10;while(top) pc(stk[top--]);}
}
using namespace IO;
const int N = 2e5+10;
int n,a[N],b[N],sum[20],id[N],id1[N],o=10,cnt=1;
signed main()
{
    read(n);
    for(int i = 1;i <= n;i++) read(a[i]),b[i]=a[i];
    for(int i = 1;i <= n;i++) sum[a[i]%o]++;//值为a[i]%o的个数有几个 
    for(int i = 1;i <= 9;i++) sum[i] += sum[i-1];//前缀 
    for(int i = n;i >= 1;i--) id[sum[a[i]%o]--] = i,a[i]/=o;
    while(cnt < 9) //最多执行最大数的位数次，也就是9次，前面已经执行了一次 
    {
        for(int i = 0;i <= 9;i++) sum[i] = 0;
        for(int i = 1;i <= n;i++) id1[i] = id[i];
        for(int i = 1;i <= n;i++) sum[a[i]%o]++;
        for(int i = 1;i <= 9;i++) sum[i] += sum[i-1];
        for(int i = n;i >= 1;i--) id[sum[a[id1[i]]%o]--] = id1[i],a[id1[i]]/=o;
        cnt++;
    }
    for(int i = 1;i <= n;i++) print(b[id[i]]),pc(' ');
    flush();
    return 0;
}