6.3 用统计数组排序

“小朋友们，统计数组不仅可以用来统计，还可以用来排序呢！”我兴奋地说，”这种排序方法叫做计数排序，特别适合数据范围不大的情况。”

6.3.1 数组元素的排序

题目描述： 对数组的元素按从小到大进行排序。

输入格式： 第一行有一个整数 n ( 5≤n≤100 )；第二行有 n 个整数，每个整数的值在 [0,1000] 的范围内。

输出格式： 输出排序后的数组。

样例输入：

8
1 2 3 6 8 3 4 5

样例输出：

1 2 3 3 4 5 6 8

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cnt[1010] = {0}, n, x;  // 统计数组和临时变量
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> x;
        cnt[x]++;  // 统计每个数出现的次数
    }
    
    for(int i = 0; i <= 1000; i++){
        while(cnt[i]--){  // 按次数输出每个数
            cout << i << " ";
        }
    }
    return 0;
}

算法解析：

1. 统计每个数字出现的次数
2. 按数值从小到大遍历，每个数值输出相应的次数
3. 这样就得到了有序的数组

6.3.2 寻找第K大数

题目描述： N 个小朋友在一起做游戏。每个小朋友在自己的硬纸板上写一个数，然后同时举起来。接着，小 y 老师提一个问题，看哪个小朋友先抢答出来。问题是，在这 N 个数中，第 K 大的是哪个数？

输入格式： 输入文件的第一行为 2 个整数，依次为 N 和 K ( K≤N≤1000 )；下面 N 行，每行为一个整数，表示从第 1 个小朋友到第 N 个朋友分别写的数（假设这些小朋友只知道 0~32767 之间的数）。

输出格式： 输出文件只有一行，就一个数，为第 K 大的那个数。

样例输入：

4 3
1
2
2
4

样例输出：

2

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cnt[35000] = {0};  // 统计数组初始化为0
    int n, k, x;
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++){
        cin >> x;
        cnt[x]++;  // 统计每个数出现的次数
    }
    
    int count = 0;  // 已经找到的数的个数
    for(int i = 32767; i >= 0; i--){  // 从大到小遍历
        while(cnt[i]--){
            count++;
            if(count == k){  // 找到第k大的数
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

算法解析：

1. 统计每个数字出现的次数
2. 从大到小遍历所有可能的数值
3. 累计已找到的数的个数，当达到k时输出对应的数值