Java实现计数排序（小白也能看懂的线性时间排序算法教程）

计数排序的适用条件

• 待排序的数据必须是整数（或可映射为整数）；
• 数据的取值范围不能太大（否则会浪费大量空间）；
• 适合用于数据范围较小但数据量较大的场景。

Java 实现计数排序

下面我们用 Java 编写一个完整的计数排序程序：

public class CountingSort {    // 计数排序主方法    public static void countingSort(int[] arr) {        // 找出数组中的最大值和最小值        int max = arr[0];        int min = arr[0];        for (int i = 1; i < arr.length; i++) {            if (arr[i] > max) max = arr[i];            if (arr[i] < min) min = arr[i];        }        // 创建计数数组，大小为 max - min + 1        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]--;            }        }    }    // 测试方法    public static void main(String[] args) {        int[] arr = {4, 2, 2, 8, 3, 3, 1};        System.out.println("排序前：");        for (int num : arr) {            System.out.print(num + " ");        }        countingSort(arr);        System.out.println("\n排序后：");        for (int num : arr) {            System.out.print(num + " ");        }    }}

代码解析

1. 找最值：先遍历数组找出最大值和最小值，用于确定计数数组的大小；
2. 计数：创建一个长度为 max - min + 1 的计数数组，统计每个数字出现的次数；
3. 重建：根据计数数组，按顺序将数字放回原数组，完成排序。

计数排序的优缺点

优点：

• 时间复杂度为 O(n + k)，比快排、归并更快（当 k 不大时）；
• 稳定排序（相同元素的相对位置不变）；
• 实现简单，逻辑清晰。

缺点：

• 只适用于整数或可离散化的数据；
• 当数据范围 k 很大时，空间开销巨大；
• 不是原地排序算法（需要额外 O(k) 空间）。

总结

通过本教程，你已经掌握了 Java 计数排序 的核心原理与实现方式。作为一种线性时间排序算法，它在特定场景下性能卓越。建议你在实际项目中根据数据特点选择合适的排序算法。

记住我们的四个关键词：Java计数排序、计数排序算法、Java排序教程 和 线性时间排序。掌握它们，你就能在面试和开发中游刃有余！

祝你编程愉快，排序无忧！