基数排序(Radix Sort)是一种非比较排序算法,它按照个位、十位、百位…的顺序依次对待排序元素进行排序。接下来,我将为您提供使用Java语言实现基数排序的代码和说明。
代码如下:
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr = { 53, 89, 150, 36, 633, 233, 71, 66, 322 };
System.out.println("Original array: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
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];
}
}
int count = 0;
while (max > 0) {
max /= 10;
count++;
}
// 创建桶
int[][] bucket = new int[10][arr.length];
// 记录每个桶中实际存放的数据个数
int[] bucketElementCount = new int[10];
// 对每一位进行排序,从个位开始
for (int i = 0, n = 1; i < count; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / n % 10;
bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
bucketElementCount[digitOfElement]++;
}
// 将桶中的数据取出来放回原数组
int index = 0;
for (int k = 0; k < bucketElementCount.length; k++) {
if (bucketElementCount[k] != 0) {
for (int l = 0; l < bucketElementCount[k]; l++) {
arr[index++] = bucket[k][l];
}
bucketElementCount[k] = 0;
}
}
}
}
}
在这个实现中,我们使用桶来存储排序元素,桶的个数为10,分别代表数字0-9。在排序的过程中,我们先找到要排序的元素中的最大值,然后确定需要排序的次数。对于每一次排序,我们按照从低位到高位的顺序,将元素存储到对应的桶中,最后将桶中的元素按照顺序取出,放回原数组。