用java写一个计数排序
时间: 2023-05-24 19:07:15 浏览: 65
以下是用Java实现计数排序的示例代码:
```java
public class CountingSort {
public static void countingSort(int[] arr) {
// 找到最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 统计每个元素出现的次数
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
// 将计数数组中的数字依次累加,得出每个数字排序后的位置
for (int i = 1; i < bucket.length; i++) {
bucket[i] += bucket[i - 1];
}
// 创建临时数组
int[] temp = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
// 找到当前元素在排序后的位置
int index = bucket[arr[i]] - 1;
temp[index] = arr[i];
bucket[arr[i]]--;
}
// 将临时数组中的元素赋值给原数组
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[i];
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 8, 0, 5, 7, 1, 3, 9, 6};
countingSort(arr);
System.out.println(Arrays.toString(arr)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
```
计数排序的时间复杂度为O(n+k),其中n为待排序序列的长度,k为序列中最大值与最小值之差加1。由于需要额外开辟一个辅助数组,因此空间复杂度为O(k)。计数排序是一种稳定的排序算法,适用于数据范围不大而值域范围较小的情况。