计数排序详解（C#实现与适用场景深度解析）

C#实现计数排序

下面是一个完整的C#计数排序实现代码，支持处理包含0或正整数的数组：

public static void CountingSort(int[] arr){    if (arr == null || arr.Length <= 1)        return;    // 找到最大值和最小值    int min = arr[0], max = arr[0];    foreach (int num in arr)    {        if (num < min) min = num;        if (num > max) max = num;    }    // 创建计数数组    int range = max - min + 1;    int[] count = new int[range];    // 统计每个元素出现的次数    foreach (int num in arr)    {        count[num - min]++;    }    // 重构原数组    int index = 0;    for (int i = 0; i < range; i++)    {        while (count[i]-- > 0)        {            arr[index++] = i + min;        }    }}

这段代码首先找出数组中的最小值和最大值，以确定计数数组的大小。然后遍历原数组进行计数，最后根据计数结果重建排序后的数组。

计数排序的适用场景限制

虽然计数排序的时间复杂度为 O(n + k)（n 是元素个数，k 是数据范围），看似非常高效，但它有以下几个关键限制，决定了它并非万能排序算法：

1. 数据必须是整数（或可映射为整数）

计数排序依赖于“索引”来统计频率，因此只能用于整数类型。如果你要排序字符串、浮点数或自定义对象，除非能将其唯一映射为连续整数，否则无法直接使用。

2. 数据范围不能太大

假设有100万个元素，但最大值是10亿，那么你需要创建一个长度为10亿的计数数组！这会消耗大量内存（约4GB），完全不现实。因此，只有当 k（数据范围）远小于 n（元素数量） 时，计数排序才高效。

3. 不适合负数较多或范围分散的数据

虽然可以通过偏移量（如上面代码中的 min）处理负数，但如果负数和正数跨度很大（例如从 -1,000,000 到 +1,000,000），依然会导致计数数组过大。

4. 稳定性要求高时需额外处理

基础版计数排序是稳定的（相同元素的相对顺序不变），但若实现不当可能破坏稳定性。在需要稳定排序的场景（如多关键字排序），必须确保计数后从右往左填充输出数组。

什么时候该用计数排序？

结合以上限制，以下是计数排序适用场景的典型例子：

• 对考试成绩（0~100分）进行排序
• 统计年龄分布（如0~120岁）
• 对小范围ID号进行排序（如1~10000）
• 作为基数排序（Radix Sort）的子过程

在这些场景中，数据范围小、类型为整数，且元素数量可能很大，此时计数排序能显著优于快速排序、归并排序等 O(n log n) 算法。

总结

计数排序是一种高效的非比较排序算法，在特定条件下（整数、小范围）表现卓越。但在实际开发中，务必评估数据特性是否符合其适用场景限制。盲目使用可能导致内存溢出或性能下降。

掌握C#计数排序的原理与边界，能让你在算法选型时更加游刃有余。记住：没有最好的算法，只有最适合的算法！

关键词：计数排序、C#计数排序、计数排序适用场景、非比较排序算法