FANGT

计数排序（Counting Sort）

作者：

fangys

计数排序是一种非比较型的排序算法。它不通过元素之间的比较来确定顺序，而是利用数组的索引来确定元素的正确位置，通过统计每个值出现的次数来实现排序。

算法原理

  1. 找出范围：找到待排序数组中的最大值和最小值，确定数据范围
  2. 统计频率：创建一个计数数组，统计每个值出现的次数
  3. 计算位置：对计数数组进行前缀和计算，得到每个值在排序后的最终位置
  4. 构建输出：根据计数数组将元素放到正确的位置

C++实现例题

基础版本

 #include <bits/stdc++.h>
 using namespace std;
 int main(){
     int n,x;
     cin>>n;
     int cnt[10005]={}; // 统计数组的大小由数据范围而定
     for(int i=1;i<=n;i++){
         cin>>x;
         cnt[x]++; // 统计次数
     }
     // 遍历统计数组时与n无关
     for(int i=0;i<10005;i++){
         if(cnt[i]!=0) cout<<i<<" "; // 排序并去重
     }
     // 遍历统计数组时与n无关
     for(int i=0;i<10005;i++){
         int j=cnt[i];
         while(j--) cout<<i<<" "; // 排序不去重
     }
     return 0;
 }

特点总结

优点：

  • 时间复杂度低，当 k = O(n) 时可以达到线性时间
  • 稳定排序
  • 不需要比较元素

缺点：

  • 需要额外的空间，空间复杂度 O(k)
  • 当数据范围 k 很大时（如 [1, 1000000] 只有几个数），效率低下
  • 只能排序整数，对于浮点数或字符串需要特殊处理

适用场景：

  • 数据范围较小且集中（k 与 n 同量级或更小）
  • 需要线性时间复杂度的稳定排序
  • 数据为整数类型

优化技巧

  1. 使用最小值偏移：避免浪费空间
  2. 选择合适的排序场景：当 k > n log n 时，考虑使用比较排序
  3. 与其他排序结合：计数排序可作为基数排序的基础