使用Java实现计数排序算法

计数排序是一种简单直观的非比较型排序算法，它通过统计每个元素出现的次数，再根据这些次数确定元素在排序后的位置。这种算法在元素范围较小且重复元素较多的场景下效率极高，非常适合初学者理解和实现。

算法核心思路¶

确定元素范围：找出待排序数组中的最小值min和最大值max，确定元素的取值范围为[min, max]。
统计元素次数：创建一个计数数组，长度为max - min + 1，用于记录每个元素出现的次数。
计算前缀和：将计数数组转换为前缀和数组，此时数组中每个位置的值表示对应元素在排序后的最后一个位置。
生成排序结果：从原数组末尾开始遍历，根据元素的计数位置将其放入结果数组，确保排序稳定性。

代码实现步骤¶

1. 处理边界情况¶

若数组为空或仅有一个元素，直接返回，无需排序。

2. 确定元素范围¶

遍历数组找到最小值min和最大值max，计算元素范围大小max - min + 1。

3. 统计元素出现次数¶

创建计数数组count，长度为max - min + 1。遍历原数组，将每个元素num映射到count[num - min]位置并计数。

4. 计算前缀和¶

对计数数组进行累加，得到每个元素在排序后的最后一个位置。

5. 生成排序结果¶

从原数组末尾遍历，根据元素的映射位置和前缀和数组，将元素放入结果数组的正确位置。

Java代码实现¶

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {
        // 边界情况处理：空数组或单元素数组无需排序
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 步骤1：找出数组中的最小值和最大值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        // 步骤2：创建计数数组，长度为max - min + 1
        int[] count = new int[max - min + 1];

        // 步骤3：统计每个元素出现的次数
        for (int num : arr) {
            count[num - min]++; // 映射元素到计数数组的索引（避免负数）
        }

        // 步骤4：计算前缀和（累加），得到每个元素的最后位置
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 步骤5：生成排序结果数组（从后往前遍历保证稳定性）
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int k = num - min; // 元素对应的计数数组索引
            result[count[k] - 1] = num; // 放置元素到结果数组的对应位置
            count[k]--; // 减少计数，为下一个重复元素腾出位置
        }

        // 将结果数组复制回原数组
        System.arraycopy(result, 0, arr, 0, arr.length);
    }

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

代码解释¶

统计次数：通过num - min将元素映射到计数数组的非负索引，避免负数索引问题。例如，元素2在min=1时，映射到索引1（2-1=1）。
前缀和计算：累加后的计数数组中，每个位置i的值表示元素min + i在排序后的最后一个位置。例如，原数组[1,2,2,3,3,4,8]的计数数组累加后为[1,3,5,6,6,6,6,7]，其中count[2]=5表示元素3（min+2=3）的最后位置是4（5-1）。
稳定性：从原数组末尾遍历，确保重复元素的相对顺序不变。例如，原数组中的两个2会按原顺序放在结果数组的第1和第2位置。

复杂度分析¶

时间复杂度：O(n + k)，其中n是数组长度，k是元素范围大小（max - min + 1）。只需遍历数组3次（统计、累加、生成结果）。
空间复杂度：O(n + k)，需要额外的计数数组和结果数组。

适用场景¶

元素为整数且范围较小（如学生分数、年龄等）。
重复元素较多，且需要保持相对顺序（稳定性）。

计数排序通过简单的计数和累加操作实现排序，无需复杂的比较逻辑，非常适合初学者理解排序算法的基本思想。