//! 基数排序

pub fn sort(data:&mut Vec<usize>){
	let n = data.len();
	let len = get_max_len(data);
	for i in 0..len{
		//获得本轮的位数d=1,10,100,1000,...
		let mut d = 1;
		for _j in 0..i{
			d *= 10;
		}
		//初始化v
		let mut v = Vec::new();
		for _j in 0..10{
			v.push(Vec::new());
		}
		//往桶里面装数
		for j in 0..n{
			let da = get_digit_of_d(data[j],d);
			v[da].push(data[j]);
		}
		//把排完的数再从桶里取出来放回到data里
		for j in 0..n{
			for vi in 0..v.len(){
				if v[vi].len() == 0{
					continue;
				}
				data[j] = v[vi].remove(0);
				break;
			}
		}
	}
}

// 获取一个数的第几位上数字，d=1时，是个位上的数，d=10时，是十位上的数
fn get_digit_of_d(data:usize,d:usize)->usize{
	(data / d) % 10
}

fn get_len(data:usize)->usize{
	let mut d = data;
	let mut l = 0;
	loop{
		l += 1;
		d /= 10;
		if d == 0{
			break;
		}
	}
	l
}

fn get_max_len(data:&Vec<usize>)->usize{
	let mut l = 0;
	for d in data{
		let dl = get_len(*d);
		if dl > l{
			l = dl;
		}
	}
	l
}
