基数排序

public class RadixSort {

	public static void main(String[] args){
	
		RadixSort rs = new RadixSort();
		int[] a ={43,35,199,54,023,334,51,29,66,28};
		rs.countSort(a,1);
//这个地方不是计数排序吗？你答对了，呵呵，先理解计数排序吧	
       }
	public int  getDigital(int num,int i){
		
//i=1,10，100，分别取个位，十位，百位上的数字
		int r = 0;
		r = num/i%10;
		return r;
		
	}
	
	public void countSort(int[] a,int weishu){
		
		int[] b = new int[a.length];
		
		if(weishu<10000){// 如果最大数是三位数，到百位上的数结束就可以了
			
			int[] c = new int[10];
			
			for (int i = 0; i < a.length; i++) {
				//weishu=1，就是按个位上的数排序，weishu=10就是按十位上的数排序，weishu=100就是按百位上 的数字排序
				c[getDigital(a[i],weishu)]++;
			}
			for (int i = 1; i < c.length; i++) {
				c[i] = c[i]+c[i-1];
			}
			for (int i = a.length-1; i >=0; i--) {
//这个地方是倒着来的，对，理解这个地方，也就理解了基数排序为什么是先按个位排序，然后在按高位上的数字排序
				
                                int numInweishu = getDigital(a[i],weishu);
				int position = c[numInweishu] -1;
				c[numInweishu]--;
				b[position] = a[i];
			}
			countSort(b,weishu*10);
//递归的调用，按个位排序完了，在按十位排....注意递归结束的条件，学算法，先理解递归吧			
		}else{
			
			for(int i = 0; i < a.length; i++) {
				System.out.println(a[i]);
//递归完了，排序也就完成了，按从小到大的顺序输出
			}
		}
		
		
	}
	
	
	
}

 

评论

2 楼 pb_water 2013-11-27  

http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html
参考这篇，很有帮助

1 楼 pb_water 2013-11-27  

一定要先理解计数排序