洛谷9_1计数排序

【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 $n$（$n\le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（$m \le 2000000$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

样例输出 #1

1 2 2 2 2 2 2 2 5 5

题解

题目简析

我们通过情景去想，直接对所有的投票结果进行排序，不如直接对每个候选人的票数进行统计，然后按照票数从小到大输出即可。

代码实现与详细注释

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    //具象表述：n个候选人，一共有m张选票
    //抽象表述：每个数都是1~n之间的数，一共有m个数
    int a[1000]={0};
    int x;
    //具象表述：候选人编号
    //抽象表述：输入的数x
    for(int i=0;i<m;i++)
    {
        cin>>x;
        a[x]++;
        //具象表述：投的是x号候选人，票数加1，建立了每个候选人和对应票数的关系
        //抽象表述：输入的是x，那么a[x]++，动态更新了每个数的对应重复次数
    }
    //另一方面，x也与a[x]建立了关系，由于下标遍历的有序性，从而无形之中把x也进行了排序
    //所以计数排序的核心不在于计数(a[x]++)，而在于建立数字与有序下标的关系
    for(int i=1;i<=n;i++)
        for(int j=1;j<=a[i];j++)//输出重复了a[x]个的x
            cout<<i<<" ";
    cout<<endl;
    return 0;
}

测试点结果

算法分析

• 时间复杂度为$O(m+n\times a[i])$，空间复杂度为$O(n)$，虽然有双重循环，但是单个数字的重复次数是有限的，因此时间复杂度可以近似为$O(m+n)$。
• 而这一种排序的核心在于建立数字与有序数组下标的映射，因此有不少a[i]都是0，因此相当于以空间换时间，而当数字的取值范围很大时，需要建遍历的有序下标的范围也会很大，因此不适用于数字取值范围很大的情况。
• 那么适用于什么情况呢？适用于数字取值范围很小，但是重复次数很多的情况，例如：成绩排序，年龄排序等。
• 如果数字取值范围很大，但是重复次数很少，例如：身份证号排序，那么计数排序就不适用了，因为空间复杂度会很大，而且时间复杂度也不会有很大的优势。
• 区别于比较排序，计数排序是一种非比较排序，还有两种非比较排序：桶排序和基数排序，这三种排序都是以空间换时间的非比较而是采取分类映射的方式进行排序的，不依赖于排序对象之间的直接大小比较。
• 但是计数排序是最简单的一种，桶排序和基数排序都是在计数排序的基础上进行了优化，因此计数排序是最基础的一种非比较排序。
• 桶排序以及基数排序的适用范围更广，后面我会专门讲解桶排序和基数排序，这里只是简单介绍一下计数排序。