计数排序-知识总结 解决问题 对一组线性存储的数据进行排序。
核心思想 计数排序是基于数值域的排序算法。通过查找比第i个元素大或小的数的个数获取第i个元素的排序位置从而实现排序。计数排序会使用额外的存储空间来统计元素出现的频率，是一种以空间换时间的算法。
工作原理 从小到大排序 原理介绍 ①计算每个数值出现了多少次 ②计算每个数值出现次数的前缀和 ③根据出现次数前缀和求数值排名
代码模板
1// 从小到大排序
2#include <bits/stdc++.h>
3using namespace std;
4
5int arr[100005] = {};
6int cnt[105] = {};
7int ans[100005] = {};
8
9int main() {
10 int n;
11 cin >> n;
12 for (int i = 0; i < n; ++i) {
13 cin >> arr[i];
14 ++cnt[arr[i]];
15 }
16 for (int i = 2; i <= 100; ++i) {
17 cnt[i] += cnt[i - 1];
18 }
19 for (int i = n - 1; i >= 0; --i) {
20 ans[--cnt[arr[i]]] = arr[i];
21 }
22 for (int i = 0; i < n; ++i) {
23 cout << ans[i] << (i + 1 == n ? "\n" : " ");
24 }
25
26 return 0;
27}从大到小排序 原理介绍 ①计算每个数值出现了多少次 ②计算每个数值出现次数的后缀和 ③根据出现次数后缀和求数值排名
代码模版
1// 从大到小排序
2#include <bits/stdc++.h>
3using namespace std;
4
5int arr[100005] = {};
6int cnt[105] = {};
7int ans[100005] = {};
8
9int main() {
10 int n;
11 cin >> n;
12 for (int i = 0; i < n; ++i) {
13 cin >> arr[i];
14 ++cnt[arr[i]];
15 }
16 for (int i = 99; i >= 1; --i) {
17 cnt[i] += cnt[i + 1];
18 }
19 for (int i = n - 1; i >= 0; --i) {
20 ans[--cnt[arr[i]]] = arr[i];
21 }
22 for (int i = 0; i < n; ++i) {
23 cout << ans[i] << (i + 1 == n ? "\n" : " ");
24 }
25 return 0;
26}算法评价 时间复杂度：O(n+w) 空间复杂度：O(n+w) 稳定性：稳定排序 更适合对n比较大，w比较小的数据进行排序，例如成绩、价格等等问题
总结作业非常重要，请务必认真完成✔️
考试只有一次提交机会，请务必本地检查正确后再提交❇️
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2174题解+参考代码 题目链接 出现次数最多的小写字母：L2174
题解 我们需要找出输入字符串中出现次数最多的小写字母，并且在出现次数相同的情况下，选择 ASCII 码值最大的那个字母。
算法步骤 读取输入：读取输入字符串。 统计字母出现次数： 使用一个长度为 26 的数组 count 来记录每个小写字母出现的次数，数组索引对应字母 'a' 到 'z'。 找出出现次数最多的字母： 遍历 count 数组，找出出现次数最多的字母，如果有多个相同次数的字母，选择 ASCII 码值最大的那个字母。 输出结果：输出出现次数最多的字母。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 string s;
7 cin >> s;
8
9 // 初始化统计数组
10 int count[26] = {0};
11
12 // 统计每个字母出现的次数
13 for (int i = 0; i < s.length(); i++) {
14 count[s[i] - 'a']++;
15 }
16
17 // 找出出现次数最多的字母
18 char maxChar = 'a';
19 int maxCount = 0;
20
21 for (int i = 0; i < 26; ++i) {
22 if (count[i] > maxCount || (count[i] == maxCount && (char)(i + 'a') > maxChar)) {
23 maxCount = count[i];
24 maxChar = (char)(i + 'a');
25 }
26 }
27
28 // 输出结果
29 cout << maxChar << endl;
30
31 return 0;
32}L2175题解+参考代码 题目链接 众数：L2175
题解 我们需要找出给定整数列表中的众数，并按照从小到大的顺序输出所有众数。众数是指在数据集中出现次数最多的数值。
算法步骤 1、读取输入：读取整数 n 和接下来的 n 个整数。 2、统计每个数出现的次数： 使用一个长度为 101 的数组 count 来记录每个数出现的次数，数组索引对应 0 到 100。 3、找出出现次数最多的数： 遍历 count 数组，找出出现次数最多的数。 4、输出结果：输出所有出现次数最多的数，并按照从小到大的顺序输出。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int nums[100];
9 int count[101] = {0};
10
11 for (int i = 0; i < n; ++i) {
12 cin >> nums[i];
13 count[nums[i]]++;
14 }
15
16 // 找出出现次数最多的数
17 int maxCount = 0;
18 for (int i = 0; i <= 100; ++i) {
19 if (count[i] > maxCount) {
20 maxCount = count[i];
21 }
22 }
23
24 // 输出结果
25 bool first = true;
26 for (int i = 0; i <= 100; ++i) {
27 if (count[i] == maxCount) {
28 if (!first) {
29 cout << " ";
30 }
31 cout << i;
32 first = false;
33 }
34 }
35 cout << endl;
36
37 return 0;
38}