【一、项目背景详细介绍】

计数排序（Counting Sort）是一种稳定的线性时间排序算法，适用于待排序元素为非负整数且范围（k）较小的场景。该算法通过统计每个值出现的次数，再累加得到每个值在有序序列中的最终位置，从而完成排序。计数排序的时间复杂度为O(n + k)，空间复杂度为O(n + k)，在k = O(n)时表现为线性时间，具有极高的效率。

计数排序常用于基数排序（Radix Sort）的子过程，也常作为其他非比较排序的基础。由于算法不依赖比较操作，避免了比较排序Ω(n log n)的下界，并且能够在许多工程场景中实现高性能排序。

【二、项目需求详细介绍】

1. 功能需求

   • 在Java环境中实现Counting Sort算法，对整型数组进行正序排序；

   • 支持数组中包含0及正整数；

   • 输出稳定排序结果，保持相等元素原有相对顺序。

2. 性能需求

   • 时间复杂度O(n + k)，其中n为元素数量，k为元素值域范围；

   • 额外空间复杂度O(n + k)，用于计数数组和输出辅助数组；

3. 代码质量需求

   • 模块化设计：包括主排序方法、计数统计、累加计算、结果输出；

   • 注释完备：说明每一步的目的和实现细节；

   • 提供测试示例：包括边界场景（空数组、单元素）、典型场景和重复元素场景。

【三、相关技术详细介绍】

1. 数组与索引操作

   • 使用原生数组存储原始数据、计数数组和输出数组；

   • 借助System.arraycopy优化数组拷贝操作；

2. 稳定性实现

   • 在输出阶段从后向前遍历原数组，保证相等元素按照原序依次放置到输出数组；

3. 空间与时间权衡

   • 计数数组长度为k+1，若k远大于n则不推荐使用；

4. 与比较排序区别

   • 计数排序不进行元素比较，通过直接索引访问实现排序，时间复杂度突破比较下界。

【四、实现思路详细介绍】

1. 统计每个元素出现次数

   • 遍历原数组，创建长度为maxValue + 1的计数数组count[]，并对每个元素值v执行count[v]++；

2. 累加计数数组

   • 将count[i]累加为count[i] + count[i-1]，此时count[i]表示值<=i的元素总数；

3. 构建输出数组

   • 创建与原数组等长的输出数组output[]；

   • 从原数组末尾向前遍历，取值v，其在输出数组中的索引为count[v] - 1，放入后执行count[v]--；

4. 拷贝回原数组

   • 将output[]的内容按序拷贝回原数组，完成排序。

【五、完整实现代码】

// 文件：CountingSort.java
// 描述：计数排序实现，稳定、线性时间

import java.util.Arrays;

public class CountingSort {

    /**
     * 对非负整数数组进行计数排序
     * @param arr 待排序数组，元素值>=0
     */
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        // 1. 查找最大值
        int max = arr[0];
        for (int v : arr) {
            if (v > max) max = v;
        }
        // 2. 计数数组
        int[] count = new int[max + 1];
        for (int v : arr) {
            count[v]++;
        }
        // 3. 累加
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        // 4. 输出数组，倒序保证稳定性
        int n = arr.length;
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int v = arr[i];
            int idx = count[v] - 1;
            output[idx] = v;
            count[v]--;
        }
        // 5. 拷贝回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    // 测试示例
    public static void main(String[] args) {
        int[] data = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始：" + Arrays.toString(data));
        countingSort(data);
        System.out.println("排序后：" + Arrays.toString(data));
    }
}

【六、代码详细解读】

• 最大值获取：遍历一次原数组确定计数数组长度；

• 计数统计：计算每个值出现次数，时间O(n)；

• 累加操作：将计数转换为位置边界，时间O(k)；

• 构建输出：倒序遍历保证稳定性，然后写入输出数组；

• 拷贝回写：使用System.arraycopy，避免手动循环，提高性能；

【七、项目详细总结】

计数排序通过对元素值域进行直接统计与累加，实现了O(n + k)的线性排序性能，并保持排序稳定性。该算法适用于元素范围不大的场景，如成绩排行、年龄分组等。在K相对较小时，计数排序较比较型排序具有显著性能优势。

【八、项目常见问题及解答】

1. 问：计数排序适用于负数吗？
   答：本实现仅支持非负整数，可通过偏移量value - min映射为非负；

2. 问：计数排序是稳定的吗？
   答：通过倒序遍历原数组并依次放置，保证相等元素原有相对顺序，故为稳定；

3. 问：当k远大于n时怎么办？
   答：不推荐使用计数排序，可选用快速排序、归并排序等O(n log n)算法；

【九、扩展方向与性能优化】

1. 负数支持：计算最小值min并将value - min映射到计数索引；

2. 泛型计数：对具有有限离散类别的对象使用映射器将其映射为索引；

3. 基数排序：将计数排序用于多位整数的低位到高位排序；

4. 并行化累加：利用并行流或多线程加速累加操作；

5. 内存压缩：使用位图或压缩存储计数数组以减少空间开销；