用Java写一个基数排序
时间: 2023-03-21 18:02:58 浏览: 61
好的,我可以回答您的问题。下面是一个Java实现的基数排序算法:
```java
public static void radixSort(int[] arr) {
// 获取最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 从个位开始,对数组进行排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 将计数数组中的值累加,得到元素的最终位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 将元素按照计数数组中的位置放到输出数组中
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// 将输出数组中的元素复制到原数组中
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
```
这是一个基数排序的标准实现,它利用了计数排序来对每个数字位上的数字进行排序。首先,我们需要获取待排序数组中的最大值,然后从个位开始对数组进行排序。在排序过程中,我们需要将每个元素按照当前数字位上的数字放入桶中,然后再按照桶中的顺序将元素输出到输出数组中。最后,将输出数组中的元素复制到原数组中即可。