计数排序进阶：不仅要排序，还要知道它排在第几位（稳定性详解）
前言
在信息学奥赛（OI）和CSP认证中，计数排序（Counting Sort）是一种非常高效的非比较排序算法。它的时间复杂度仅为O(n+w)（其中w是值域），在处理值域较小整数排序时，速度远超快速排序。
很多同学学会了如何用桶统计频率并输出排序结果，但在遇到“输出原数组中每个元素在排序后所处的位置”这类问题时，往往会卡在如何保证稳定性上。
今天我们就结合一道经典例题，来讲讲计数排序的核心——前缀和与倒序遍历。
问题描述
给定n个正整数，请将它们从小到大排序，然后输出。
进阶要求：并且输出原来每个数字排序后在第几位（对于相同的数字，序号小的排在前面）。
样例输入：
5 3 9 5 3 2样例输出：
2 3 3 5 9 2 5 4 3 1(解释：原数组第1个是3，排序后排在第2位；第2个是9，排序后排在第5位...)
核心逻辑解析
计数排序不仅是“数数”，它的完整形态包含三个步骤：
统计频率：
c[x]++，统计数字x出现了几次。前缀和（关键）：
c[i]+=c[i-1]。做完这一步，
c[x]的含义发生了质变：它不再是x的个数，而是x在有序数组中最后一次出现的位置（右边界）。比如样例中，数字3出现了 2 次。做完前缀和后，
c[3]=3，意味着所有数字 3 应该排在第2位和第3位，且最后一个3必须坐在第3把交椅上。
倒序确定排名（稳定性）：
为什么要从n到1倒着遍历原数组？
因为前缀和数组
c[x]告诉我们要把x放在最靠后的位置。当我们遇到原数组中靠后出现的x时，应该把它填入当前x能占用的最大位置，然后将
c[x]--（把这个位置封死，留给前面出现的x）。这样就完美保证了：原数组中靠后的，排序后依然靠后（稳定性）。
完整代码
//排序 用记数排序来写 #include <iostream> #include <algorithm> //max和min函数 using namespace std; int n; int a[100010];//愿数组 int c[100010];//前缀和数组，记录小于等于i的数字有多少个 int r[100010];//记录原来第i个数排完序后的位置 int ma=0; int mi=0x3f3f3f3f; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; c[a[i]]++; ma=max(ma,a[i]);//找原数中的最大值 mi=min(mi,a[i]);//找原数中的最小值 } //第一步先输出排序后的序列 for(int i=mi;i<=ma;i++){ for(int j=1;j<=c[i];j++){ cout<<i<<" "; } } cout<<endl; //第二步处理：计算排名（核心） //c[i]现在的含义是：数值小于等于i的元素一共有多少个 //也就是数值i在排序后能达到的最大位置（右边界） //对c数组做前缀和，求出小于等于i的数有多少个 for(int i=2;i<=ma;i++){ c[i]+=c[i-1]; } //倒序遍历原数组，确定每个数的排名 //必须倒着做，这是保证算法稳定性的关键 for(int i=n;i>=1;i--){ //a[i]是当前要处理的数字 //c[a[i]]是它当前可用的最靠后的位置 //占用了这个位置后，该数字的可用位置就要向前移一位 r[i]=c[a[i]]--; } //输出每个原位置数字的排名 for(int i=1;i<=n;i++){ cout<<r[i]<<" "; } }总结
数据范围：计数排序受限于值域。本题中
，空间完全够用。如果
很大（如 10^9），则需要使用
map或离散化，或者改用sort。空间换时间：这是典型的用空间换时间的算法。
易错点：
前缀和循环的范围不要越界。
最重要的一点：最后填充
r[i]时，一定要写i=n循环到1。虽然顺着写在某些特定题目（不需要稳定性）也能过，但养成倒序遍历的习惯是理解基数排序的基础。