请给出基数排序java版代码带注释和解释,最后输出结果
时间: 2024-02-13 10:01:13 浏览: 27
好的,下面是基数排序的Java代码,注释和解释也会一并给出:
```java
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr = {53, 3, 542, 748, 14, 214};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 获取数组中最大值的位数
int maxDigit = getMaxDigit(arr);
// 对每一位进行排序
for (int i = 1; i <= maxDigit; i++) {
// 用桶来存储每个位上的数字
int[][] buckets = new int[10][arr.length];
int[] count = new int[10];
// 将数组中的数字放入对应的桶中
for (int j = 0; j < arr.length; j++) {
int digit = getDigit(arr[j], i);
buckets[digit][count[digit]] = arr[j];
count[digit]++;
}
// 将桶中的数字按顺序放回原数组中
int index = 0;
for (int j = 0; j < count.length; j++) {
for (int k = 0; k < count[j]; k++) {
arr[index] = buckets[j][k];
index++;
}
}
}
}
// 获取数字的某一位上的数字
private static int getDigit(int num, int digit) {
return (num / (int) Math.pow(10, digit - 1)) % 10;
}
// 获取数组中最大值的位数
private static int getMaxDigit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int num : arr) {
max = Math.max(max, num);
}
return String.valueOf(max).length();
}
}
```
基数排序的思路是将待排序的数组按照每一位上的数字进行排序,从低位到高位依次进行排序,直到排完最高位为止。
具体实现步骤如下:
1. 先获取数组中最大值的位数。
2. 对每一位进行排序,用桶来存储每个位上的数字。先遍历数组,将数组中的数字放入对应的桶中。
3. 将桶中的数字按顺序放回原数组中。
4. 重复步骤2和步骤3,直到排完最高位为止。
输出结果为:`[3, 14, 53, 214, 542, 748]`