java 基数排序
时间: 2023-11-18 09:53:50 浏览: 54
好的,关于 Java 基数排序,我可以给你一些简单的介绍。
Java 基数排序是一种非比较排序算法,它通过将待排序元素按照位数切割成不同的数字,然后按照每个位数分别比较。具体来说,它将所有待比较数值统一为同样的数位长度,数位较短的数前面补零,然后从最低位开始,依次进行一次排序,这样从最低位排序一直到最高位排序完成后,数列就变成一个有序序列。
Java 基数排序的时间复杂度为 O(d(n+r)),其中 d 是数字位数,n 是待排序元素个数,r 是基数。虽然时间复杂度比较高,但是它的空间复杂度比较低,是一种稳定的排序算法。
下面是 Java 基数排序的代码实现:
```
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
List<List<Integer>> bucketList = new ArrayList<>();
for (int i = 0; i < 10; i++) {
bucketList.add(new ArrayList<>());
}
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < arr.length; j++) {
int num = (arr[j] % mod) / div;
bucketList.get(num).add(arr[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
List<Integer> bucket = bucketList.get(j);
for (int k = 0; k < bucket.size(); k++) {
arr[index++] = bucket.get(k);
}
bucket.clear();
}
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)