基数排序－java实现

  
/**
 * 基数排序
 * 
 * @author timmy1
 *
 */
public class RadixSort {
	/**
	 * 实现思路：根据传入的位数进行循环： 第一遍：先循环数组中元素个位数上的数字，先根据个位数进行排序，使用二维数组进行数据存放
	 * 第二遍：进行元素十位数上的数字排序
	 * 
	 * @param array
	 *            数组
	 * @param radix
	 *            基数，存放 0－9共十个数字
	 * @param bit
	 *            位数；表示个位，十位，百位
	 */
	private void radixSort(int[] array, int radix, int bit) {
		int divid = 1;// 进行求个位十位数字上的元素大小，每次bit循环都自乘10
		int length = array.length;
		List<ArrayList<Integer>> datas = new ArrayList<ArrayList<Integer>>();
		
		for(int h=0;h<10;h++){
			List<Integer> lists = new ArrayList<Integer>();
			datas.add((ArrayList<Integer>) lists);
		}
		
		for (int i = 1; i <= bit; i++) {
			// 每次循环都将上List数据清空
			int size = datas.size();
			for(int j = 0;j<size;j++){
				datas.get(j).clear();
			}
			
			for (int j = 0; j < length; j++) {// 求个数上的数字
				int data = array[j];// 拿到
				int key = (data / divid) % radix;
				datas.get(key).add(data);
			}
			// 将digit数组中的元素取出来，放到array数组中去
			int index = 0;
			for (int j = 0; j < 10; j++) {
				List<Integer> digits = datas.get(j);
				int m = digits.size();
				for(int n = 0;n<m;n++){
					array[index++] = digits.get(n);
				}
			}
			PrintUtil.print("第"+i+"趟排序");
			PrintUtil.printArray(array, PrintUtil.HORIZONTAL);
			divid *= 10;
		}
	}
	
	public static void main(String[] args) {
		int[] array = { 188, 61, 98, 566, 48, 75, 12, 0, 234, 32, 65, 10 };
		PrintUtil.print("基数排序");
		PrintUtil.printArray(array, PrintUtil.HORIZONTAL);
		RadixSort radixSort = new RadixSort();
		radixSort.radixSort(array, 10, 3);
	}
}