所谓计数排序, 就是建立在计数上的排序.
计数排序不以比较为基础, 所以可以打破比较排序 \(O(nlogn)\) 的复杂度下界.
我们只要计算出比 \(i\) 小的数字有多少个, 就可以知道 \(i\) 在数据里的排名. 然后根据排名, 我们就可以反造一波排好序的数据了.
我们用 \(rk[i]\) 记录第 \(i\) 个数据的排名,\(sum[i]\) 记录权值 1~\(i\) 一共有多少个数据. 然后 \(a[i]\) 的排名就是 \(sum[i]\), 如果有相同的权值那么每次用 \(sum[i]\) 更新一个数据的 \(rk\) 后都要把 \(sum[i]\)--.
那么根据 \(ans[rk[i]]=a[i]\), 一个一个把数据往 \(ans\) 数组里填就是了.
时间复杂度:\(O(n+maxv)\)
空间复杂度:\(O(n+maxv)\)
代码如下:
- #include <cstdio>
- using namespace std;
- const int maxn=1e6+5;
- int n,rk[maxn];
- int a[maxn],b[maxn],sum[maxn];
- 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;
- }
- int main() {
- n=read();
- for(int i=1;i<=n;i++)
- a[i]=read(),sum[a[i]]++;
- for(int i=1;i<=n;i++)
- sum[i]=sum[i]+sum[i-1];// 利用前缀和求 sum
- for(int i=1;i<=n;i++)
- rk[i]=sum[a[i]]--;// 求 rk[i]
- for(int i=1;i<=n;i++)
- b[rk[i]]=a[i];// 求 rk 的反数组
- for(int i=1;i<=n;i++)
- printf("%d",b[i]);//rk 的反数组就是排好序的数据
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2768139.html