# Java怎么实现计数排序 计数排序（Counting Sort）是一种非比较型的排序算法，特别适用于整数数据的排序场景。本文将详细介绍计数排序的原理、Java实现步骤、复杂度分析以及实际应用示例。 ## 一、计数排序算法原理 ### 1.1 基本思想 计数排序的核心思想是通过统计数组中每个元素出现的次数，然后根据统计结果将元素放回正确位置。与基于比较的排序算法（如快速排序、归并排序）不同，计数排序利用元素的实际值确定其在输出数组中的位置。 ### 1.2 适用条件 - **数据范围有限**：需要知道待排序数组的最大值（或范围） - **整数类型数据**：通常用于正整数排序（可通过偏移处理负数） - **稳定性要求**：可以设计为稳定排序（保持相同元素的原始顺序） ## 二、计数排序实现步骤 ### 2.1 算法流程 1. **找出最大值**：确定统计数组的长度 2. **统计频次**：遍历原数组，统计每个元素出现次数 3. **计算位置**：将频次数组转换为前缀和数组 4. **反向填充**：根据统计结果将元素放入输出数组 ### 2.2 Java代码实现 ```java public class CountingSort { public static void sort(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 1. 找出数组中的最大值 int max = arr[0]; for (int num : arr) { if (num > max) { max = num; } } // 2. 初始化计数数组 int[] count = new int[max + 1]; // 3. 统计每个元素出现次数 for (int num : arr) { count[num]++; } // 4. 计算元素最终位置（前缀和） for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // 5. 创建临时数组存储排序结果 int[] output = new int[arr.length]; // 6. 反向填充保证稳定性 for (int i = arr.length - 1; i >= 0; i--) { int num = arr[i]; output[count[num] - 1] = num; count[num]--; } // 7. 将结果拷贝回原数组 System.arraycopy(output, 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)); sort(arr); System.out.println("排序后: " + Arrays.toString(arr)); } } public static void sortWithNegative(int[] arr) { // 找出最大值和最小值 int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); // 计算计数数组大小 int range = max - min + 1; int[] count = new int[range]; // 统计元素出现次数（使用偏移量） for (int num : arr) { count[num - min]++; } // 计算前缀和 for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } // 构建输出数组 int[] output = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { int num = arr[i]; output[count[num - min] - 1] = num; count[num - min]--; } System.arraycopy(output, 0, arr, 0, arr.length); } 其中： - n 是待排序元素个数 - k 是数据范围（最大值-最小值+1）
上述实现是稳定排序，因为反向填充时保持了相同元素的原始顺序。
// 生成随机测试数组 int[] largeArr = new int[1000000]; Random rand = new Random(); for (int i = 0; i < largeArr.length; i++) { largeArr[i] = rand.nextInt(100); // 限制范围在0-99 } // 比较计数排序与Arrays.sort() long start = System.currentTimeMillis(); CountingSort.sort(largeArr.clone()); long end = System.currentTimeMillis(); System.out.println("计数排序耗时: " + (end - start) + "ms"); start = System.currentTimeMillis(); Arrays.sort(largeArr.clone()); end = System.currentTimeMillis(); System.out.println("快速排序耗时: " + (end - start) + "ms"); 测试结果示例（100万数据，范围0-99）：
计数排序耗时: 25ms 快速排序耗时: 120ms // 不使用前缀和的简化版（非稳定） public static void simpleSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int[] count = new int[max + 1]; for (int num : arr) count[num]++; int index = 0; for (int i = 0; i <= max; i++) { while (count[i] > 0) { arr[index++] = i; count[i]--; } } } class Student { String name; int score; // 构造方法等... } public static void sortStudents(Student[] students) { // 假设分数范围0-100 int[] count = new int[101]; // 统计分数频次 for (Student s : students) { count[s.score]++; } // 计算前缀和 for (int i = 1; i <= 100; i++) { count[i] += count[i - 1]; } Student[] output = new Student[students.length]; // 反向填充保持稳定性 for (int i = students.length - 1; i >= 0; i--) { int score = students[i].score; output[count[score] - 1] = students[i]; count[score]--; } System.arraycopy(output, 0, students, 0, students.length); } 通过找出最小值，将所有元素减去最小值转换为非负数，排序后再加回偏移量（见2.3节实现）。
因为它通过计算而不是元素比较来确定顺序，突破了O(nlogn)的比较排序下限。
当k远大于n时，可考虑： 1. 使用桶排序或基数排序 2. 缩小范围（如对数字按位处理）
计数排序是处理小范围整数排序的高效算法，其Java实现需要注意边界条件、负数处理和稳定性维护。虽然应用场景有限，但在特定场景下性能远超通用排序算法。理解计数排序有助于掌握更复杂的线性时间排序算法（如基数排序），也是算法学习的经典案例。 “`
文章结构说明： 1. 从原理到实现层层递进 2. 包含基础实现和优化版本 3. 补充复杂度分析和实际测试 4. 通过Q&A解决常见疑问 5. 保持技术深度同时保证可读性 6. 严格控制在约2300字（实际MD源码约2000字，渲染后约2300字）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
