算法概述
计数排序（Counting Sort）是一种非比较型的线性时间排序算法，由 Harold H. Seward 于1954年提出。与传统的基于比较的排序算法（如快速排序、归并排序）不同，计数排序的核心思想是利用待排序元素本身的值作为数组下标，通过统计每个元素出现的次数来实现排序。当待排序数据的取值范围相对集中时，计数排序可以达到 O(n + k) 的时间复杂度，其中 n 为元素个数，k 为数据取值范围的大小。
计数排序属于稳定排序，这意味着相等元素的原始相对顺序在排序后会被保留。这一特性使其成为基数排序（Radix Sort）等高级排序算法的重要子过程。本文将深入讲解计数排序的原理，并用 Java 实现基础版与稳定版两种变体，同时展示其在频率统计中的实战应用。
核心原理
计数排序的工作流程可分为三个关键步骤：
第一步：统计频率
遍历原始数组，使用一个辅助数组 count[] 记录每个数值出现的次数。count[i] 表示数值 i 在原始数组中出现了多少次。
第二步：计算前缀和
将 count[] 转换为前缀和数组。转换后，count[i] 表示小于等于 i 的元素总共有多少个。这一步是确定每个元素在最终输出数组中位置的关键。
第三步：反向填充输出数组
从原始数组的末尾开始遍历（保证稳定性），根据 count[] 数组确定每个元素在输出数组中的确切位置，将其放入对应位置后，将 count[] 中对应值减一。
为什么需要反向填充？
反向填充是保证排序稳定性的关键。假设原始数组中有两个值为 5 的元素，后出现的那个 5 在 count[] 中对应的位置更靠前。从后向前遍历，后出现的 5 会先被放置到输出数组中更靠后的位置，从而保持了原始相对顺序。
基础版计数排序 Java 实现
基础版计数排序适用于非负整数场景，直接根据元素值作为数组下标进行统计。
/**
* 基础版计数排序实现
* 适用于非负整数数组，不保证稳定性
*/
public class CountingSortBasic {
/**
* 对非负整数数组进行排序
* @param arr 待排序数组
* @return 排序后的新数组（原数组不变）
*/
public static int[] sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr == null ? null : arr.clone();
}
// 第一步：找出数组中的最大值，确定计数数组的大小
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 创建计数数组，下标范围 0 ~ max
int[] count = new int[max + 1];
// 第二步：统计每个元素出现的频率
for (int num : arr) {
count[num]++;
}
// 第三步：根据计数数组重构排序结果
int[] result = new int[arr.length];
int index = 0;
for (int i = 0; i < count.length; i++) {
// 数值 i 出现了 count[i] 次，依次写入结果数组
while (count[i] > 0) {
result[index++] = i;
count[i]--;
}
}
return result;
}
public static void main(String[] args) {
int[] data = {4, 2, 2, 8, 3, 3, 1, 0, 4, 2};
System.out.println("原始数组: " + java.util.Arrays.toString(data));
int[] sorted = sort(data);
System.out.println("排序结果: " + java.util.Arrays.toString(sorted));
// 输出: [0, 1, 2, 2, 2, 3, 3, 4, 4, 8]
}
}
基础版的优点是代码简洁、空间占用相对较小；缺点是无法处理负数，且不保证排序稳定性（相同元素的原始顺序可能被改变）。
稳定版计数排序 Java 实现
稳定版计数排序通过引入偏移量处理负数，并采用反向填充策略保证稳定性。
/**
* 稳定版计数排序实现
* 支持负数，保证排序稳定性
*/
public class CountingSortStable {
/**
* 对整数数组进行稳定排序
* @param arr 待排序数组
* @return 排序后的新数组（原数组不变）
*/
public static int[] sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr == null ? null : arr.clone();
}
// 第一步：找出最大值和最小值，确定取值范围
int max = arr[0];
int min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
// 计算偏移量：将所有数值映射到非负下标
int offset = -min;
int range = max - min + 1;
// 创建计数数组，下标范围 0 ~ (max - min)
int[] count = new int[range];
// 第二步：统计频率（使用偏移后的下标）
for (int num : arr) {
count[num + offset]++;
}
// 第三步：计算前缀和，count[i] 表示小于等于该值的元素个数
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 第四步：反向遍历原数组，根据前缀和确定位置，填充输出数组
int[] result = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int value = arr[i];
// 该值在输出数组中的位置 = count[value + offset] - 1
int position = count[value + offset] - 1;
result[position] = value;
// 位置占用后减一，保证下一个相同值放在前面
count[value + offset]--;
}
return result;
}
public static void main(String[] args) {
int[] data = {-3, 1, -5, 0, 2, -3, 1, 4, -1, 2};
System.out.println("原始数组: " + java.util.Arrays.toString(data));
int[] sorted = sort(data);
System.out.println("稳定排序: " + java.util.Arrays.toString(sorted));
// 输出: [-5, -3, -3, -1, 0, 1, 1, 2, 2, 4]
}
}
稳定版通过 offset 偏移量巧妙解决了负数处理问题，同时利用前缀和 + 反向填充的经典范式，确保了相等元素的原始相对顺序不变。
频率统计实战应用
计数排序的核心数据结构——频率数组，本身就是最强大的频率统计工具。以下展示如何利用计数排序的思想，高效完成成绩分段统计、字符频率分析等常见任务。
import java.util.*;
/**
* 基于计数排序思想的频率统计工具类
*/
public class FrequencyAnalyzer {
/**
* 统计整数数组中每个值的出现频率
* @param arr 输入数组
* @return Map<数值, 出现次数>
*/
public static Map<Integer, Integer> frequencyMap(int[] arr) {
Map<Integer, Integer> freq = new LinkedHashMap<>();
if (arr == null || arr.length == 0) return freq;
// 找出范围
int max = arr[0], min = arr[0];
for (int v : arr) {
if (v > max) max = v;
if (v < min) min = v;
}
int offset = -min;
int[] count = new int[max - min + 1];
// 统计频率
for (int v : arr) {
count[v + offset]++;
}
// 按数值大小顺序输出频率（天然有序）
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
freq.put(i - offset, count[i]);
}
}
return freq;
}
/**
* 学生成绩分段统计
* 将 0~100 分的成绩按 10 分为一段进行统计
*/
public static void gradeStatistics(int[] scores) {
// 10 个分数段：0-9, 10-19, ..., 90-100
int[] segments = new int[11];
for (int score : scores) {
int seg = Math.min(score / 10, 10);
segments[seg]++;
}
System.out.println("===== 成绩分段统计 =====");
for (int i = 0; i < 10; i++) {
System.out.printf("%2d-%2d 分: %d 人%n", i * 10, i * 10 + 9, segments[i]);
}
System.out.printf("90-100分: %d 人%n", segments[10]);
}
/**
* 字符频率统计（支持 ASCII 字符）
*/
public static void charFrequency(String text) {
int[] freq = new int[128]; // ASCII 范围
for (char c : text.toCharArray()) {
if (c < 128) {
freq[c]++;
}
}
System.out.println("===== 字符频率统计 =====");
for (int i = 0; i < freq.length; i++) {
if (freq[i] > 0) {
System.out.printf("'%c' : %d 次%n", (char) i, freq[i]);
}
}
}
public static void main(String[] args) {
int[] scores = {85, 92, 78, 65, 88, 92, 71, 85, 99, 55, 68, 82};
System.out.println("频率统计: " + frequencyMap(scores));
gradeStatistics(scores);
String text = "Hello, Counting Sort!";
charFrequency(text);
}
}
复杂度分析
| 指标 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 最优情况 | O(n + k) | O(k) | k 为数据取值范围 |
| 最坏情况 | O(n + k) | O(k) | 与数据分布无关 |
| 平均情况 | O(n + k) | O(k) | 始终线性 |
| 稳定性 | 稳定 | — | 反向填充保证稳定性 |
其中 n 为待排序元素个数，k 为 max - min + 1（数据取值范围大小）。
适用场景
- 数据范围集中：当 k ≈ n 或 k < n 时，计数排序效率极高。
- 整数或离散数据：元素必须是可映射为数组下标的离散值。
- 作为子过程：稳定版计数排序是基数排序（Radix Sort）的必备基础。
- 频率统计需求：需要同时获取排序结果和每个值的出现次数。
不适用场景
- 数据范围极大：若 k >> n（如稀疏的大范围数据），空间开销会过大。
- 浮点数排序：需要通过缩放因子映射为整数，可能引入精度问题。
- 对象排序：对象本身不能直接作为数组下标，需提取可排序的键值。
算法扩展：基数排序的基石
计数排序最重要的应用之一是作为基数排序的底层排序过程。基数排序通过从低位到高位（或反之）逐位排序，将时间复杂度优化到 O(d × (n + k))，其中 d 为数字的位数。由于每一位的排序需要保证稳定性，稳定版计数排序恰好满足这一要求。
/**
* 基数排序简化示意：利用稳定计数排序对每一位进行排序
*/
public class RadixSortDemo {
public static void radixSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 找到最大值，确定最大位数
int max = arr[0];
for (int v : arr) if (v > max) max = v;
// 从个位开始，对每一位进行稳定计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
private static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10]; // 每一位只有 0~9
// 统计当前位上的数字频率
for (int value : arr) {
int digit = (value / exp) % 10;
count[digit]++;
}
// 前缀和
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 反向填充（保证稳定性）
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
}
总结
计数排序以其 O(n + k) 的线性时间复杂度，在排序算法家族中占据独特地位。它打破了基于比较排序的 Ω(n log n) 下界，通过空间换时间的策略，在数据范围集中时展现出无与伦比的效率。
本文实现了基础版与稳定版两种计数排序，并展示了其在频率统计中的实战价值。理解计数排序的关键在于掌握频率统计 → 前缀和 → 反向定位的三段式思维框架，这一框架不仅适用于排序本身，也是解决各类离散数据统计问题的通用利器。
