计数排序(Counting Sort)

1. 计数排序介绍

1.1 基本思路和使用场景

应用背景：计数排序适用于取值范围较小，但是有较多重复数值的场景。

基本思路：找到每个数值对应的总排名。根据总排名，依次存储到output数组中。计数排序不是基于比较的排序算法。

1.2 算法描述

1. 找出待排序的数组（记为arr）中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入计数数组（记为count）的第i项；
3. 对所有的计数累加（从count中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

1.3 算法过程示例

原始数组（4, 2, 2, 8, 3, 3, 1）的计数排序的具体过程如下：

1. 找到原始数组arr的最大元素max

2. 初始化count数组，长度为max+1，所有元素为0，用于存储0~max数值出现的次数。

3. 遍历原始数组，将每个元素出现的次数存储到count数组中。
   • 例如，元素3出现了2次，数组count的下标3的位置（count[3]）就存储为2。
   • 例如，数值5没有出现，对应的位置（count[5]）就为0。

4. 将count数组所有的值累加，这样每个位置就表示截止当前数值的总排名，即索引位置。对于有重复的，按照累加的规则，会取最大排名值。例如，有两个3，其排名最小值是4，最大值是5，这里会存5。

5. 遍历原始数组arr
   1. 对每个数值arr[i]在count数组中找到对应值count[arr[i]]（即总排名）。 例如，对于arr[0]（值为4），查count数组，可以得4的排名为6。
   2. 其数值count[arr[i]]（即总排名）减1作为output数组的索引，值arr[i]存储到output数组中。例中，元素4存储到output[5]中。
   3. 考虑到有重复元素，将元素放到对应的位置后，计数器count[arr[i]]减1。例中，count[4]减一。

2. 代码示例

#include <iostream>
using namespace std;
const int maxn = 100000;  //数组的最大长度
const int maxs = 1000;  //最大的取值范围[0~1000)，不含1000
int output[maxn]; //输出数组

void countSort(int array[], int size) {
  int count[maxs] = {0};   //每个数值出现的次数，初始化为0
  // 记录每个数值出现的次数
  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  // 直接输出示例：遍历计数数组，输出结果
    for (int i=0; i<maxs; i++) {
        for (int j=0; j<count[i];j++) {
            cout<< i << " ";
        }
    }
    cout << endl;

  // 出现的次数累加
  for (int i = 1; i <= maxs; i++) {
    count[i] += count[i - 1];
  }

  // 一般不需要output数组，以下仅供查找对应排名的参考（直接输出的示例见上）：
  // 1. 对原始数组的每个元素（array[i]，设为a），在count数组中count[a]，即它的排名位置（设为rank）。
  // 2. 将元素a存储到output[rank-1]中即可。减一（-1）是由于数组索引从0开始。
  // 3. for循环*逆序*，在array为struct等场景（如成绩表），便于排序稳定。
  // 4. 由于有重复元素，count[a]中记录的是最大排名，故找到元素后，排名减少1。
  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }
}

int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(array) / sizeof(array[0]);
  countSort(array, n);
  for (int i = 0; i < n; i++)
    cout << output[i] << " ";
  cout << endl;
}

3. 练习

1、

【CSP 2019 入门组第一轮 q20】（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。

例如有三对整数$(3,4)$、$(2,4)$、$(3,3)$,那么排序之后应该是$(2,4)$、$(3,3)$、$(3,4)$ 。

输入第一行为$n$,接下来$n$行，第$i$行有两个数$a[i]$和$b[i]$,分别表示第$i$对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围 $1<n<10^7$, $1<a[i],b[i]<10^4$

提示：应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第二关键字排序的结果，数组res[]存储双关键字排序的结果。

试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i) 
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

1）①处应填（）
A. ++cnt [i]   B. ++cnt[b[i]]  
C. ++cnt[a[i] * maxs + b[i]]   D. ++cnt[a[i]]  

2）②处应填（）
A. ord[--cnt[a[i]]] = i   B. ord[--cnt[b[i]]] = a[i]  
C. ord[--cnt[a[i]]] = b[i]   D. ord[--cnt[b[i]]] = i  

3）③处应填（）
A. ++cnt[b[i]]   B. ++cnt[a[i] * maxs + b[i]]  
C. ++cnt[a[i]]   D. ++cnt [i]  

4）④处应填（）
A. res[--cnt[a[ord[i]]]] = ord[i]  
B. res[--cnt[b[ord[i]]]] = ord[i]  
C. res[--cnt[b[i]]] = ord[i]  
D. res[--cnt[a[i]]] = ord[i]  

5）⑤处应填（）
A. a[i], b[i]  
B. a[res[i]], b[res[i]]  
C. a[ord[res[i]]], b[ord[res[i]]]  
D. a[res[ord[i]]], b[res[ord[i]]]  

4. 编程练习

1. csp-j-20-2 直播获奖，可以参考计数排序的部分思路。

5. 参考代码

5.1 csp-j-20-2 直播获奖

简洁实现：

#include <iostream> //cin, cout
#include <stdio.h>  //printf
#include <cmath>    //max
#define MAX_SCORE 600
using namespace std;

int main()
{
  int n; //选手总数
  int w; //获奖率
  cin >> n >> w;

  int counter[MAX_SCORE + 1] = {0}; //每个分数的选手数量
  int curr_prize_n = 0;             //当前获奖人数
  int curr_baseline = 0;            //当前分数线
  int tmp_score = 0;                //当前输入的分数

  for (int p = 1; p <= n; p++) //当前已评出了p个选手
  {
    //计数统计
    scanf("%d", &tmp_score); //测试提升性能 cin >> tmp_score;
    //该分数段的总数+1
    counter[tmp_score]++;
    //计算分数线
    curr_prize_n = max(1, p * w / 100);

    //找分数线对应的位置，该实现为性能不调优的版本，用全部重新累计的办法计算
    //其他思路：为提升性能，可以记住上一次的分数线和对应的人数，减少for循环
    int sum_n = 0;
    for (int i = MAX_SCORE; i >= 0; i--)
    {
      sum_n += counter[i];
      if (sum_n >= curr_prize_n)
      {
        //输出分数线
        printf("%d", i); //提升性能，不用cout
        if (p < n)
          printf(" ");
        break;
      }
    }
  }
  return 0;
}

性能优化版本：

#include <iostream>
#include <cmath>
#include <stdio.h>
#define MAX_SCORE 600
using namespace std;

int main()
{
  int n; //选手总数
  int w; //获奖率
  cin >> n >> w;

  int counter[MAX_SCORE + 1] = {0}; //每个分数的选手数量
  int curr_prize_n = 0;             //当前获奖人数
  int tmp_score = 0;                //当前输入的分数

  int prize_score = MAX_SCORE + 1; //上一次获奖的分数线
  int prize_score_n = 0;           //上一次获奖的分数线对应的累计总人数，从高分到低分累积

  for (int p = 1; p <= n; p++) //当前已评出了p个选手
  {
    scanf("%d", &tmp_score); //测试提升性能 cin >> tmp_score;

    counter[tmp_score]++;
    curr_prize_n = max(1, p * w / 100); //当前需要获奖的人数

    //分数线
    if (tmp_score >= prize_score)
      prize_score_n++;

    //找到一个分数线，其累积的人数不少于需要获奖的人数，而分数线+1的累积人数则不够
    while (!(prize_score_n >= curr_prize_n && prize_score_n - counter[prize_score] < curr_prize_n))
    {
      if (prize_score_n >= curr_prize_n) //上一个分数线，对应的获奖人数过多，或者下一个分数对应的人数为0.
      {
        prize_score_n -= counter[prize_score];
        prize_score++;
      }
      else //上一个分数线，对应的获奖人数不足
      {
        prize_score--;
        prize_score_n += counter[prize_score];
      }
    }
    //输出分数线
    printf("%d", prize_score); //测试提升性能  cout << prize_score;
    if (p < n)
      printf(" "); //cout << " ";
  }
  return 0;
}