计数排序

算法定义

计数排序（Counting Sort）是一种非比较型排序算法，它通过统计每个元素出现的次数，然后根据次数信息重新构建有序数组。与比较型排序（如快速排序）不同，计数排序不依赖元素间的比较，而是利用元素的值作为数组下标来直接确定其位置，因此效率极高。

计数排序适用于元素值范围较小且为整数的场景（如年龄、成绩等）。

算法思路

计数排序的核心步骤如下：

确定范围：找出数组中的最大值和最小值，计算数据范围（range = max - min + 1）。
计数统计：创建计数数组，统计每个元素出现的次数。
计算前缀和：将计数数组转换为前缀和数组，确定每个元素在结果数组中的起始位置。
构建结果：从原数组末尾向前遍历，根据前缀和数组将元素放入结果数组的正确位置，并递减对应计数。

例如，排序[4, 2, 2, 8, 3, 3, 1]：

计数数组：[1, 2, 2, 1, 0, 0, 0, 1]（索引对应元素值）
前缀和数组：[1, 3, 5, 6, 6, 6, 6, 7]
结果数组：[1, 2, 2, 3, 3, 4, 8]

算法复杂度

最好时间复杂度：O (n + range) - n 为元素个数，range 为数据范围（max - min + 1）
最坏时间复杂度：O (n + range) - 与最好情况相同，不受数据分布影响
平均时间复杂度：O(n + range)
空间复杂度：O (n + range) - 需要存储计数数组和结果数组

优点与缺点

优点：
- 时间复杂度低，接近线性时间 O (n)
- 稳定的排序算法（相等元素相对位置不变）
- 实现简单，无复杂逻辑
- 适合并行计算
缺点：
- 仅适用于整数或可映射为整数的离散值
- 当数据范围（range）远大于元素个数（n）时，空间效率极低
- 无法直接排序小数、字符串等非整数类型
- 需要提前知道数据的范围

应用场景

元素值为整数且范围较小的场景（如 0-100 的成绩排序）
作为基数排序的子排序算法
对稳定性要求高的排序场景
数据量大但值域范围有限的场景（如统计用户年龄分布）

各版本优化说明

基本版：
- 适用于已知最大值的非负整数排序
- 实现简单，清晰展示计数排序的核心思想
- 需要提前知道数据的最大值，灵活性较低
自动计算范围优化：
- 自动获取数据的最大最小值，无需手动指定范围
- 通过偏移量处理负数，扩展了适用范围
- 保持稳定性，适合更多实际场景
原地计数排序优化：
- 直接在原数组上重建排序结果，减少空间开销
- 空间复杂度优化为 O (range)，适合内存受限场景
- 牺牲了稳定性，但空间效率更高
分段计数排序优化：
- 当数据范围过大时，将数据分成多个段分别排序
- 避免了创建过大的计数数组，降低空间复杂度
- 适合处理大范围但分布较分散的数据

计数排序是一种在特定场景下表现极佳的排序算法，当数据范围较小时，其效率远超比较型排序算法。实际应用中，常作为基数排序的子过程，或用于处理值域有限的整数排序场景。

代码

import java.util.Arrays;

public class CountingSort {
    
    // 1. 基本版计数排序（处理非负整数，已知范围）
    public static void countingSortBasic(int[] arr, int maxValue) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        int[] result = new int[n];
        int[] count = new int[maxValue + 1]; // 计数数组
        
        // 统计每个元素出现的次数
        for (int num : arr) {
            count[num]++;
        }
        
        // 计算前缀和，确定每个元素的起始位置
        for (int i = 1; i <= maxValue; i++) {
            count[i] += count[i - 1];
        }
        
        // 从后往前遍历，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int num = arr[i];
            result[count[num] - 1] = num;
            count[num]--;
        }
        
        // 复制结果到原数组
        System.arraycopy(result, 0, arr, 0, n);
    }
    
    // 2. 优化版1：自动计算范围（支持任意整数，包括负数）
    public static void countingSortAutoRange(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值和最小值，确定范围
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) {
                min = num;
            }
            if (num > max) {
                max = num;
            }
        }
        
        int range = max - min + 1;
        int n = arr.length;
        int[] result = new int[n];
        int[] count = new int[range];
        
        // 统计次数（偏移处理负数）
        for (int num : arr) {
            count[num - min]++;
        }
        
        // 计算前缀和
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建结果数组（从后往前保证稳定性）
        for (int i = n - 1; i >= 0; i--) {
            int num = arr[i];
            result[count[num - min] - 1] = num;
            count[num - min]--;
        }
        
        // 复制回原数组
        System.arraycopy(result, 0, arr, 0, n);
    }
    
    // 3. 优化版2：原地计数排序（减少空间开销）
    public static void countingSortInPlace(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        
        int range = max - min + 1;
        int[] count = new int[range];
        
        // 统计次数
        for (int num : arr) {
            count[num - min]++;
        }
        
        // 直接在原数组中重建排序结果
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min;
                count[i]--;
            }
        }
    }
    
    // 4. 优化版3：适用于大规模数据的分段计数排序
    public static void countingSortSegmented(int[] arr, int segmentSize) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        
        int range = max - min + 1;
        // 如果范围较小，直接使用普通计数排序
        if (range <= segmentSize) {
            countingSortAutoRange(arr);
            return;
        }
        
        // 计算分段数量
        int segmentCount = (range + segmentSize - 1) / segmentSize;
        int[][] segments = new int[segmentCount][0];
        
        // 将元素分配到不同段
        for (int num : arr) {
            int segmentIndex = (num - min) / segmentSize;
            segments[segmentIndex] = addElement(segments[segmentIndex], num);
        }
        
        // 对每个段单独排序并合并
        int index = 0;
        for (int[] segment : segments) {
            if (segment.length > 0) {
                countingSortAutoRange(segment);
                System.arraycopy(segment, 0, arr, index, segment.length);
                index += segment.length;
            }
        }
    }
    
    // 辅助方法：动态添加元素到数组
    private static int[] addElement(int[] arr, int element) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = element;
        return arr;
    }
    
    public static void main(String[] args) {
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1};
        int[] arr2 = {-3, -1, 2, 0, -3, 5, 2};
        int[] arr3 = {4, 2, 2, 8, 3, 3, 1};
        int[] arr4 = {10, 20, 5, 15, 30, 25, 5, 10, 35};
        
        countingSortBasic(arr1, 8);
        System.out.println("基本版（已知范围）: " + Arrays.toString(arr1));
        
        countingSortAutoRange(arr2);
        System.out.println("自动计算范围（支持负数）: " + Arrays.toString(arr2));
        
        countingSortInPlace(arr3);
        System.out.println("原地计数排序: " + Arrays.toString(arr3));
        
        countingSortSegmented(arr4, 10);
        System.out.println("分段计数排序: " + Arrays.toString(arr4));
    }
}