jdk中如何实现计数排序

# JDK中如何实现计数排序

## 一、计数排序算法概述

计数排序（Counting Sort）是一种非比较型的线性时间排序算法，其核心思想是通过统计数组中每个元素出现的次数，然后根据统计结果将元素放回正确位置。该算法时间复杂度为O(n+k)，其中n是元素个数，k是数据范围大小。

### 算法特点
1. **稳定排序**：相同元素的相对顺序保持不变
2. **非比较排序**：不依赖元素间的比较操作
3. **适用范围有限**：适合整数且范围不大的数据集

## 二、JDK中的实现分析

虽然JDK标准库中没有直接提供计数排序的实现，但我们可以通过分析Arrays.sort()在特定场景下的优化来理解类似思想的应用。

### 2.1 针对字节数组的优化

在JDK的`Arrays.sort(byte[] a)`实现中，当数组长度超过29时，会使用计数排序的变种：

```java
// JDK 17中的相关实现片段
if (length > 29) {
    int[] count = new int[256]; // byte范围是-128~127
    
    // 统计每个元素出现次数
    for (byte b : a) {
        count[b + 128]++;
    }
    
    // 根据统计结果重写数组
    int idx = 0;
    for (int i = 0; i < count.length; i++) {
        byte value = (byte)(i - 128);
        for (int j = 0; j < count[i]; j++) {
            a[idx++] = value;
        }
    }
}

2.2 实现关键步骤

1. 初始化计数数组：创建足够覆盖所有可能值的计数数组
2. 频率统计：遍历原数组统计每个元素出现次数
3. 重构数组：根据计数数组按顺序填充元素

三、完整实现示例

以下是标准的计数排序Java实现：

public static void countingSort(int[] arr) {
    if (arr.length == 0) return;
    
    // 1. 确定范围
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    // 2. 创建并填充计数数组
    int[] count = new int[range];
    for (int num : arr) {
        count[num - min]++;
    }
    
    // 3. 计算位置前缀和（稳定排序关键）
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // 4. 构建输出数组
    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    
    // 5. 拷贝回原数组
    System.arraycopy(output, 0, arr, 0, arr.length);
}

四、算法优化与变种

4.1 空间优化

可以省略输出数组，直接在原数组上操作：

// 修改最后两步为原地排序
int idx = 0;
for (int i = 0; i < range; i++) {
    while (count[i]-- > 0) {
        arr[idx++] = i + min;
    }
}

4.2 处理负数

通过偏移量处理（如JDK示例中的+128）：

// 假设处理包含负数的byte数组
int offset = -min; // min是负数
count[arr[i] + offset]++;

五、性能分析

六、适用场景与限制

适用场景

1. 整数排序且范围较小（k与n同数量级）
2. 需要稳定排序的场景
3. 作为基数排序的子过程

局限性

1. 不适用于浮点数排序
2. 数据范围过大时空间消耗显著
3. 需要额外处理负数

七、总结

虽然JDK没有直接暴露计数排序API，但在特定场景（如byte数组排序）中采用了类似思想。理解计数排序的实现有助于我们： 1. 掌握非比较排序的核心原理 2. 在合适场景选择更高效的排序策略 3. 深入理解JDK底层优化技术

实际开发中，当需要处理有限范围的整数排序时，可以考虑实现自定义的计数排序来获得性能提升。 “`