您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 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进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。