排序算法(七)基数排序
基数排序法是属于稳定性的排序O (nlog(r)m),其中r为所采取的基数(桶树),而m为堆数( 位数)
有如下数组:
第一趟:
我们首先对这个数组按照其个位数进行分组,结果如下:
然后将分组后的数据按照索引的大小取出,得到新的数组如下:
第一趟排序后完成的工作为将数组按照个位数由小到大的顺序进行了排序
第二趟:
对第一趟的结果按照十位数进行分组,结果如下:
然后将分组后的数组按照索引的大小分别取出,得到新的数组如下:
第二趟排序后完成的工作是将数组按照十位数由小到大进行了排序,同时由于个位数已经进行了排序,因此将分组后的数组按照索引大小取出时,十位数相同的较小的会排在前面,如31和38,43和49
第三趟:
对第二趟的结果按照百位数进行分组,结果如下:
然后将分组后的数组按照索引的大小分别取出,得到新的数组如下:
第三趟排序后完成的工作是将数组按照百位数由小到大进行了排序,同时由于个位数和十位数都已经进行了排序,所以较小的数会排在前面
这样就完成了整个数组的排序.
例如现在我们要将下列一组数进行排序: {13,25,1111,232,4454,79,86,98,61,447};
1)先按照个位数字进行排序,排序后结果为{1111,61,232,13,4454,25,86,447,98,79}
2) 然后再按照十位进行排序,排序结果为{1111,13,25,232,447,4454,61,79,86,98}
3)然后按照百位进行排序,如果百位为空,则认为百位为0,排序结果为{13,25,61,79,86,98,1111,232,447,4454}
4)最后按照千位排序,排序结果为{13,25,61,79,86,98,232,447,1111,4454}*/
public class BaseSort {
public static void main(String[] args) {
int[] a = {13,25,1111,232,4454,79,86,98,61,447};
System.out.println("初始值:");
print(a);
a=sort(a);
System.out.println("\n排序后:");
print(a);
}
public static int[] sort(int[] data){
int maxLength = getMaxLength(data);
int[] tmp = baseSort(data,0,maxLength);
return tmp;
}
/**
* @param data
* @param i
* @param maxLength
* @return
*/
private static int[] baseSort(int[] data, int i, int maxLength) {
if(i>=maxLength){
return data;
}
int len = data.length;
//创建10个桶,每个桶中分别用来存放第i位为0~9得数子个数
//例如i=0,count[1],就用来存放各位为1得数字个数
int[] count = new int[10];
//用来复制数组,辅助排序
int[] tmp = new int[len];
//将数组中所有得数按照规则放入同种
for (int j = 0; j < tmp.length; j++) {
count[getNum(data[j], i)]++;
}
//将count[]数字代表桶中数字得个数,变为下标
//例如:count[0]原来为1个,count[1]为1个,那么count[1]后面一位得下表就是count[0]+count[1]=2
for (int j = 1; j < count.length; j++) {
count[j] = count[j-1]+count[j];
}
//将原数组总元素按照顺序复制到新数组中
for (int j = tmp.length-1; j >= 0; j--) {
int number = data[j];
int a = getNum(number, i);
tmp[count[a]-1]=number;
count[a]--;
}
return baseSort(tmp, i+1, maxLength);
}
/**
* 获取一个数字第i位得数字,个位从0开始
* @param num
* @param i
* @return
*/
private static int getNum(int num,int i){
for (int j = 0; j < i+1; j++) {
if(j==i){
num%=10;
}else{
num=num/10;
}
}
return num;
}
/**
* 获取数组得长度
* @param num
* @return
*/
private static int length(int num){
return String.valueOf(num).length();
}
/**
* 查找数组总所有得元素拥有得最大长度
* @param data
* @return
*/
private static int getMaxLength(int[] data){
int maxLength = 0 ;
for (int i = 0; i < data.length; i++) {
if(maxLength<length(data[i])){
maxLength = length(data[i]);
}
}
return maxLength;
}
private static void print(int[] a){
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}