计数排序算法及其应用(C++)

发布于 2020-09-22  460 次阅读


数排序算法是一种非比较算法,即通过这种算法排序过程中比较次数为0,并且它的时间复杂度为O(n),低于许多排序算法,但是空间复杂度较高,是一种牺牲空间复杂度来提高时间复杂度的算法。
算法原理很简单,开辟一个全部初始化为0的新数组,数组长度大于等于待排序数组的最大值,直接把待排序数组作为新数组下标,若某下标出现则新数组对应元素自增。下面是一个计数排序的简单例子,假设没有重复元素并且待排序数组元素最大值小于100.

#include<iostream>
using namespace std;
int b[100];
#define n 10
int main(){
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
b[a[i]]=1;
}
for(int i=0;i<100;i++)
{
int j=0;
if(b[i]==1)a[j]=i;
j++;
}
for(int i=0;i<10;i++)
cout<<a[i]<<endl;

return 0;
}

如果数组内有重复元素则修改计数为自增,排序过程为循环自减至0即可。
关于这种排序的应用,比如洛谷 P2141 珠心算测验 这道题。下面贴上题干。

题目描述
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

(本题目为2014NOIP普及T1)

输入格式
共两行,第一行包含一个整数nn,表示测试题中给出的正整数个数。

第二行有nn个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。

输出格式
一个整数,表示测验题答案。

第一个题解(来自AK_Automata)便是计数排序的应用:

#include<iostream>
#include<cstdio>
using namespace std;
const int M=20005;//20005由于最大值是10000+10000=20000,const int是静态定义,定义后该值(即M)无法修改。
int t[M],g[M];//t是桶,t[i]表示值为i的数在集合中两两相加出现了几次,g[i]表示值为i的数是否在原集合中,1为在,0为不在
int n,a[105],ans,maxn;//a数组开105是由于总共最多100个数
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];//读入
        g[a[i]]=1;//在集合中赋值为1
    }
    for (int i=1;i<n;i++){//暴力枚举求出可以加出的数
        for (int j=i+1;j<=n;j++){
            t[a[i]+a[j]]++;//a[i]+a[j]这个数被加出来了
            maxn=max(maxn,a[i]+a[j]);//求求出数中最大值
        }
    }
    for (int i=1;i<=maxn;i++){//只需要枚举到最大值即可
        if (t[i]>0&&g[i]) ans++;//判断是否满足,满足就ans++
    }
    cout<<ans<<endl;
    return 0;
}

华科计科学生。 想法很多,技术很少。