排序系列（七）--基数排序

?

import java.util.ArrayList;

?

//author：lilywangcn

public class RadixSort {

//private static int[] array={36,5,16,98,95,47,32,36,48};

private static int[] array={614,738,921,485,637,101,215,530,790,306};

/**

* @param args

*/

?

public static void main(String[] args) {

// TODO Auto-generated method stub

ArrayList[] arrayradix=new ArrayList[10];

for(int k=0;k<10;k++){

arrayradix[k]=new ArrayList();

}

int key=0;

for(int i=0;i<3;i++){

for(int j=0; j<array.length; j++){

int numkey=getKey(array[j],10,i);

switch(numkey){

case 0:arrayradix[0].add(array[j]);break;

case 1:arrayradix[1].add(array[j]); break;

case 2:arrayradix[2].add(array[j]);break;

case 3:arrayradix[3].add(array[j]); break;

case 4:arrayradix[4].add(array[j]); break;

case 5:arrayradix[5].add(array[j]); break;

case 6:arrayradix[6].add(array[j]); break;

case 7:arrayradix[7].add(array[j]); break;

case 8:arrayradix[8].add(array[j]); break;

case 9:arrayradix[9].add(array[j]); break;

}

}

int m=0;

for(int k=0;k<10;k++){

for(int j=0;j<arrayradix[k].size();j++){

array[m++]=(Integer)arrayradix[k].get(j);

}

arrayradix[k].clear();

}

print();

}

}

private static int getKey(int num, int radix, int position){

if (position ==0) return num%radix;

else return (num/getnum(position,radix))%radix;

}

private static int getnum(int position, int radix){

int result=radix;

for(int i=1;i<position;i++)

result*=radix;

return result;

}

private static void print(){

for(int i=0;i<array.length;i++){

System.out.print(array[i]+" ");

}

System.out.println("");

}

?

}

算法的时间复杂度：O(d*n),d为数字的最大位数。算法稳定
运行结果：530 790 921 101 614 485 215 306 637 738?101 306 614 215 921 530 637 738 485 790?101 215 306 485 530 614 637 738 790 921?