【Java -- 算法】十大排序算法之基数排序

简介

基数排序是另外一种比较有特色的排序方式，它不需要直接对元素进行相互比较，也不需要将元素相互交换，你需要做的就是对元素进行“分类”。

基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
(1) 分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）
(2) 收集，再将放置在0~9号桶中的数据按顺序放到数组中
重复(1)(2)过程，从个位到最高位（比如32位无符号整形最大数4294967296，最高位10位）

实例

1. Java 代码

public class Main
{
public static void main(String[] args) {
int[] a = {13,25,1111,232,4454,79,86,98,61,447};
System.out.println("初始值:");
printArray(a);
a= sort(a);
System.out.println("\n排序后:");
printArray(a);
}

public static int[] sort(int[] data) {
int maxLength = getMaxLength(data);
int[] temp = baseSort(data,0,maxLength);
return temp;
}

private static int[] baseSort(int[] data,int i,int maxLength) {
if(i >= maxLength) {
return data;
}

int len = data.length;

int[] count = new int[10];

int[] temp = new int[len];

for (int j = 0;j < temp.length;j++) {
count[getNum(data[j],i)]++;
}

for (int m = 1;m < count.length;m++) {
count[m] = count[m - 1] + count[m];
}

for(int n = temp.length - 1;n >= 0;n--) {
int number = data[n];
int a = getNum(number,i);
temp[count[a] - 1] = number;
count[a]--;
}

return baseSort(temp, i+1, maxLength);
}

/**
* 获取一个数字第i位得数字,个位从0开始
*/
private static int getNum(int num,int i) {
for(int j = 0;j < i + 1;j++) {
if (j == i) {
num %= 10;
} else {
num /= 10;
}
}

return num;
}

private static int getMaxLength(int[] a) {
int maxLength = 0;
for (int i = 0;i < a.length;i++) {
if(maxLength < length(a[i])) {
maxLength = length(a[i]);
}

}

return maxLength;
}

/**
* 获取数组的长度
*/
private static int length(int num) {
return String.valueOf(num).length();
}

private static void printArray(int[] a) {
for (int i = 0;i < a.length;i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}

2. 输出结果