浅谈计数排序

2021-06-28 17:07

阅读：748

标签：const inline 更新 mes cst 利用 std using 数据

所谓计数排序，就是建立在计数上的排序。

计数排序不以比较为基础，所以可以打破比较排序\(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 
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‘9‘;ch=getchar())if(ch==‘-‘)f=-1;
    for(;ch>=‘0‘&&ch

浅谈计数排序

标签：const inline 更新 mes cst 利用 std using 数据

原文地址：https://www.cnblogs.com/AKMer/p/9649032.html

上一篇：学习python课程第四天

下一篇：vue.js 创建组件子父通信父子通信非父子通信

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：浅谈计数排序
文章链接：http://soscw.com/index.php/essay/98994.html

亲，登录后才可以留言！

浅谈计数排序

评论

热门文章

推荐文章

最新文章

置顶文章