核心内容摘要
工业电源模块选型参考：VB6-24S05P 与 URB2405ZP-6WR3 性能兼容解析
前言在信息学奥赛OI和CSP认证中计数排序Counting Sort是一种非常高效的非比较排序算法。
它的时间复杂度仅为O(nw)其中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 ma0; int mi0x3f3f3f3f; int main() { cinn; for(int i1;in;i){ cina[i]; c[a[i]]; mamax(ma,a[i]);//找原数中的最大值 mimin(mi,a[i]);//找原数中的最小值 } //第一步先输出排序后的序列 for(int imi;ima;i){ for(int j1;jc[i];j){ couti ; } } coutendl; //第二步处理计算排名核心 //c[i]现在的含义是数值小于等于i的元素一共有多少个 //也就是数值i在排序后能达到的最大位置右边界 //对c数组做前缀和求出小于等于i的数有多少个 for(int i2;ima;i){ c[i]c[i-1]; } //倒序遍历原数组确定每个数的排名 //必须倒着做这是保证算法稳定性的关键 for(int in;i1;i--){ //a[i]是当前要处理的数字 //c[a[i]]是它当前可用的最靠后的位置 //占用了这个位置后该数字的可用位置就要向前移一位 r[i]c[a[i]]--; } //输出每个原位置数字的排名 for(int i1;in;i){ coutr[i] ; } }
总结数据范围计数排序受限于值域。
本题中空间完全够用。
如果很大如 10^9则需要使用map或离散化或者改用sort。
空间换时间这是典型的用空间换时间的算法。
易错点前缀和循环的范围不要越界。
最重要的一点最后填充r[i]时一定要写in循环到1。
虽然顺着写在某些特定题目不需要稳定性也能过但养成倒序遍历的习惯是理解基数排序的基础。