嘿，各位编程界的探索者们，今天咱们来聊一个既简单又高效的排序算法——计数排序（Counting Sort）！想象一下，如果算法世界也有人口普查，那计数排序绝对是个条理清晰、效率奇高的“统计员”。
-
基本信息：计数排序是一种稳定的排序算法。计数排序使用一个额外的数组 ，其中第 个元素是待排序数组 中值等于i的元素的个数。然后根据数组 来将A中的元素排到正确的位置。它只能对整数进行排序。核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
-
时间复杂度：在最佳和最坏情况下，计数排序都是，其中是待排序数组的长度，k是数组中元素的最大值。这简直就像是给数组做了个“全身扫描”，速度嗖嗖的。
-
空间复杂度：计数排序的空间复杂度为，因为它需要一个大小为的辅助数组来存放每个元素的出现次数。这就好比给每个可能的数值都准备了一个“小盒子”，虽然有点占地方，但效率高啊！
-
稳定性算法：计数排序是稳定的，这意味着如果两个元素相等，它们在排序后的相对位置不会改变。就像是一群排队买票的人，即使身高相同，谁先来谁就在前面，公平公正。
现在，你是不是已经对计数排序产生了浓厚的兴趣？别急，咱们继续深入，看看它的原理是如何让人拍案叫绝的。
计数排序的原理其实超级直观，就像我们小时候玩的分类游戏一样。假设你有一堆颜色各异的积木，想要把它们按照颜色分类，最快的方法不就是每种颜色放一堆吗？计数排序也是这个思路，只不过它处理的是数字。
- 找出最大值：首先，遍历一遍待排序数组，找出数组中的最大值，这个最大值将决定辅助数组的大小。
- 初始化辅助数组：创建一个大小为最大值+1的辅助数组（为啥+1？因为数组索引从0开始嘛），并将所有元素初始化为0。这个辅助数组就像是一个“计数器”，记录每个数字出现的次数。
- 填充辅助数组：再次遍历待排序数组，每遇到一个数字，就在辅助数组对应索引的位置上加1。这样，辅助数组就记录下了每个数字的出现次数。
- 构建排序结果：最后，根据辅助数组的信息，依次将数字填入结果数组中。比如，如果辅助数组在索引2的位置上有3个，那就意味着数字2在结果数组中要连续出现3次。
-
栗子1：数组[4, 2, 2, 8, 3, 3, 1]
- 找出最大值：8
- 初始化辅助数组：[0, 0, 0, 0, 0, 0, 0, 0, 0]（因为最大值是8，所以数组长度为9）
- 填充辅助数组：[0, 1, 2, 2, 1, 0, 0, 0, 1]（根据原数组更新）
- 构建排序结果：[1, 2, 2, 3, 3, 4, 8]（按照辅助数组的信息）
-
栗子2：数组[5, 3, 8, 3, 1, 7, 9, 2, 5]
- 找出最大值：9
- 初始化辅助数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]（因为最大值是9，所以数组长度为10）
- 填充辅助数组：[1, 1, 1, 0, 2, 0, 1, 0, 1, 1]（根据原数组更新）
- 构建排序结果：[1, 2, 3, 3, 5, 5, 7, 8, 9]（按照辅助数组的信息）
怎么样，是不是觉得计数排序既简单又巧妙？接下来，咱们来看看如何在不同的编程语言中实现它。
怎么样，是不是觉得每种语言的实现都各有千秋，但都同样简洁高效？接下来，咱们来点实战，看看在洛谷上如何用计数排序解决具体问题。
优化版计数排序
正常版本的计数排序当有几个相同元素时，会改变原来元素相对位置，是不稳定排序，因此需要优化。
3.1 优化的思路
主要是将排序数组sortArr里非零元素作为权值依次加入到后面元素里。具体示例如下所示：
排序数组sortArr总共弄有334个元素
sortArr: 0 1 2 3 4 5 6 7 8 9 10 … 87 … 99 … 333
count: 2 2 2 0 0 1 1 0 1 0 1 0 1 0 1 0 1
变化后排序数组sortArr(Di == Di-1 + Di-2 : 后面的元素等于前面非零元素之和)
第333次变化后的排序数组sortArr的值即是输出有序数组的下标，索引即是缩放后的元素。代码实现如下：
for (auto& it : sortArr) // 遍历排序数组，将前面非零元素依次累加到后面
{
if (it)
tmp += it; // 非零则累加
it = tmp; // 变化后元素
}
// 经过上面的变化，此时排序数组sortArr的元素即为初始数组元素排序后的位置
那么问题来了，该如何还原排序后元素呢？
答案很简单，因为变化后排序数组sortArr的值是原始数组nums元素排序后索引下标，所以只需要依次遍历原始数组nums，然后找打对应下标，将该原始数组的元素依次取出排列到有序数组即可，代码实现如下：
for (int i = nums.size(); i > 0; --i) // 逆序遍历原始数组，找到对应位置输出有序数组
{
int index = sortArr[nums[i - 1]] - 1; // 找到元素nums[i-1]排序后位置索引；sortArr[ nums[i-1] ]的值表示元素nums[i-1]在有序数组中排第几个位置
result[index] = nums[i - 1];
sortArr[nums[i - 1]]–; // 排序数组取出一个元素排列后，该元素的值需要减一，即如果下次还命中该相同元素，则往后一位排列
}
nums = result;
3.2 优化计数排序跟基本计数排序主要区别
3.2.1变化后的排序数组sortArr存储的元素值不同
基本计数排序的排序数组sortArr存储的是初始化数组nums每个元素个数，而优化后计数排序sortArr的元素存储的是初始化数组nums排序后的位置（即排序后在第几位）
3.2.2遍历排序数组sortArr取元素方式不一样
基本计数排序主要是依次遍历排序数组sortArr，当其值非零时取元素并且该值减一，而优化计数排序主要是逆向遍历原始数组nums，通过在排序数组sortArr中找到原始数组nums每个元素的下标，而赋值给结果数组result
基本计数排序主要区别：
在洛谷上，有很多适合用计数排序解决的问题，这里咱们挑几个典型的题目进行讲解。
虽然题目要求的是快速排序，但咱们可以用计数排序来“秀一把”。注意，这里只是为了展示计数排序的应用，实际比赛中还是要根据题目要求选择合适的算法哦！
题目描述：
给出n个数，找出这n个数的中位数，并将它们从小到大排序。
解题思路：
- 首先，用计数排序对数组进行排序。
- 然后，根据排序后的数组直接找到中位数。
C++代码实现：
注意：这里的代码假设输入的n为奇数，直接取排序后数组的中间元素作为中位数。如果n为偶数，可以根据题目要求取中间两个数的平均值或其他处理方式。
通过今天的讲解，我们不仅了解了计数排序的基本信息、原理和实现方法，还通过洛谷上的例题看到了它在解决实际问题中的潜在应用（尽管有时不是直接应用）。计数排序以其简洁高效的特点，在特定场景下（如数据范围较小）能够发挥巨大作用。希望大家能够掌握这一算法，并在实际编程中灵活运用它。