1.基數(shù)排序介紹
基數(shù)排序是將整數(shù)按照位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較有梆。
2.思路分析：
上面的概念還是比較難懂的骆撇，通過例子來講一下。比如一組數(shù)據(jù)arr={53,3,542,748,14,214},使用基數(shù)排序進(jìn)行升序排序羽德。首先需要準(zhǔn)備10個(gè)數(shù)組（桶）几莽，0-9分別對(duì)應(yīng)位數(shù)的0-9。
第一輪：
- 得到每個(gè)整數(shù)的個(gè)位數(shù)宅静，比如53的個(gè)位數(shù)為3章蚣，就53放入到下標(biāo)為3的桶中
- 然后從0-9個(gè)桶中按照元素加入的順序?qū)⒃厝〕觯湃氲皆葦?shù)組中姨夹。
一輪排序后： arr={542,53,3,14,214,748}
第二輪：
得到每個(gè)整數(shù)的十位數(shù)纤垂，重復(fù)第一輪步驟。比如3的十位數(shù)為0磷账，將3放入到下標(biāo)為0的桶中峭沦。
第二輪排序后：arr = {3,14,214,542,748,53}
第三輪：
得到每個(gè)整數(shù)的百位數(shù)，重復(fù)上述步驟逃糟。比如542的百位數(shù)為5吼鱼，將542放入到小標(biāo)為5的桶中。
第三輪排序后：arr = {3,14,53,214,542,748}
至此排序結(jié)束绰咽。
3.推導(dǎo)過程
package com.yc.day04;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int arr[] = {53,3,542,748,14,214};
radixSort(arr);
}
public static void radixSort(int[]arr){
//定義一個(gè)二維數(shù)組來存儲(chǔ)是10個(gè)桶,
// 因?yàn)椴恢矫總€(gè)桶中具體會(huì)存多少個(gè)元素菇肃，所以定義桶的大小為arr.length
int [][] bucket = new int[10][arr.length];
//定義一個(gè)一維數(shù)組來記錄每個(gè)桶中有多少個(gè)元素
int [] elementCount = new int[10];
//第一輪
for (int i = 0; i < arr.length; i++) {
//得到個(gè)位數(shù)
int digit = arr[i]%10;
//將元素放到對(duì)應(yīng)的桶中
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] +=1;
}
//將各個(gè)桶中的元素取出，放到原始數(shù)組中
int index = 0;
for (int j = 0; j < elementCount.length; j++) {
if (elementCount[j] != 0) {
for (int k = 0; k < elementCount[j]; k++) {
arr[index] = bucket[j][k];
index++;
}
}
//將桶清空
elementCount[j] = 0;
}
System.out.println("第一輪排序后："+ Arrays.toString(arr));
//========================================
//第二輪
for (int i = 0; i < arr.length; i++) {
int digit = arr[i]/10%10;
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] +=1;
}
index = 0;
for (int j=0;j<elementCount.length;j++){
if(elementCount[j]!=0){
for(int k=0;k<elementCount[j];k++){
arr[index] = bucket[j][k];
index++;
}
}
//將第j個(gè)桶清空
elementCount[j] = 0;
}
System.out.println("第二輪排序后："+ Arrays.toString(arr));
//第三輪
for(int i=0;i<arr.length;i++){
int digit = arr[i]/10/10%10;
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] ++;
}
index = 0;
for(int j=0;j<elementCount.length;j++){
if(elementCount[j]!=0){
for(int k=0;k<elementCount[j];k++){
arr[index] = bucket[j][k];
index++;
}
}
elementCount[j] = 0;
}
System.out.println("第三輪排序后："+ Arrays.toString(arr));
}
}
4.完整代碼
package com.yc.day04;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int arr[] = {53,3,542,748,14,214};
radixSort(arr);
}
public static void radixSort(int[]arr){
//定義一個(gè)二維數(shù)組來存儲(chǔ)是10個(gè)桶,
// 因?yàn)椴恢矫總€(gè)桶中具體會(huì)存多少個(gè)元素取募，所以定義桶的大小為arr.length
int [][] bucket = new int[10][arr.length];
//定義一個(gè)一維數(shù)組來記錄每個(gè)桶中有多少個(gè)元素
int [] elementCount = new int[10];
//得到最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i]>max){
max = arr[i];
}
}
int maxLength = (max+"").length();
for(int i=0,n=1;i<maxLength;i++,n*=10){
//將元素按照個(gè)位琐谤、十位、百位等等存入到對(duì)應(yīng)的桶中
for(int j=0;j<arr.length;j++){
int digit = arr[j]/n%10;
bucket[digit][elementCount[digit]] = arr[j];
elementCount[digit]++;
}
//依次從桶中取出元素放入到原數(shù)組中
int index = 0;
for(int k=0;k<elementCount.length;k++){
if(elementCount[k]!=0){
for(int m = 0;m<elementCount[k];m++){
arr[index] = bucket[k][m];
index++;
}
}
//清空桶
elementCount[k] = 0;
}
System.out.println("第"+i+1+"輪基數(shù)排序后:"+Arrays.toString(arr));
}
/**
//第一輪
for (int i = 0; i < arr.length; i++) {
//得到個(gè)位數(shù)
int digit = arr[i]%10;
//將元素放到對(duì)應(yīng)的桶中
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] +=1;
}
//將各個(gè)桶中的元素取出玩敏，放到原始數(shù)組中
int index = 0;
for (int j = 0; j < elementCount.length; j++) {
if (elementCount[j] != 0) {
for (int k = 0; k < elementCount[j]; k++) {
arr[index] = bucket[j][k];
index++;
}
}
//將桶清空
elementCount[j] = 0;
}
System.out.println("第一輪排序后："+ Arrays.toString(arr));
//========================================
//第二輪
for (int i = 0; i < arr.length; i++) {
int digit = arr[i]/10%10;
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] +=1;
}
index = 0;
for (int j=0;j<elementCount.length;j++){
if(elementCount[j]!=0){
for(int k=0;k<elementCount[j];k++){
arr[index] = bucket[j][k];
index++;
}
}
//將第j個(gè)桶清空
elementCount[j] = 0;
}
System.out.println("第二輪排序后："+ Arrays.toString(arr));
//第三輪
for(int i=0;i<arr.length;i++){
int digit = arr[i]/10/10%10;
bucket[digit][elementCount[digit]] = arr[i];
elementCount[digit] ++;
}
index = 0;
for(int j=0;j<elementCount.length;j++){
if(elementCount[j]!=0){
for(int k=0;k<elementCount[j];k++){
arr[index] = bucket[j][k];
index++;
}
}
elementCount[j] = 0;
}
System.out.println("第三輪排序后："+ Arrays.toString(arr));
**/
}
}
