基数排序简介
基数排序又称桶排序，第一轮从个位数开始，先对根据个位数的位数分别放入对应的“桶”中，取出放入原数组完成第一轮排序；第一轮排完序过后，从十位数开始根据十位数的大小放入对应的“桶”中，位数不够的补0，完成第二轮排序。依次类推，直到最大的位数比较完为止
基数排序图解思路
比如有这样一个数组：
arr[]={53,3,542,748,14,214}
第一轮排序：
第一轮排序后的结果为：arr[]={542,53,3,14,214,748}
第二轮排序：
第二轮排序后的结果为：arr[]={3,14,214,542,748,53}
第三轮排序：
第三轮排序后的结果为：arr[]={3,14,53,214,542,748}
代码思路
int arr[] = {
53, 3, 542, 748, 14, 214};
int max = arr[0]; //假设第一数就是最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int[][] bucket = new int[10][arr.length];//初始化桶
int[] bucketElementCounts = new int[10];//记录每个桶放入的个数
//第1轮(针对每个元素的个位进行排序处理)
for (int j = 0; j < arr.length; j++) {
//取出每个元素的个位的值
int digitOfElement = arr[j] / 1 % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];//放入对应的桶中
bucketElementCounts[digitOfElement]++;//放完数据之后指针前移一位
}
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] != 0) {
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;//取出元素之后将桶的计数归零
}
System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
//第2轮(针对每个元素的十位进行排序处理)
for (int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / 10 % 10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] != 0) {
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;
}
System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
//第3轮(针对每个元素的百位进行排序处理)
for (int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] != 0) {
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;
}
System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr));
最终代码
int arr[] = {
53, 3, 542, 748, 14, 214};
int max = arr[0]; //假设第一数就是最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int[][] bucket = new int[10][arr.length];//初始化桶
int[] bucketElementCounts = new int[10];//记录每个桶放入的个数
int maxLength = (max + "").length();
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//取出每个元素的个位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];//放入对应的桶中
bucketElementCounts[digitOfElement]++;//放完数据之后指针前移一位
}
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] != 0) {
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;//取出元素之后将桶的计数归零
}
System.out.println("第"+i+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: