基数排序

时间复杂度为O(k*n)的排序算法。目前只适用于非负整数，当然改造下也可用于负整数。

	/**
	 * 过程：1、从个位数起，使用计数排序作为内排序方法，针对各个数位即“基数”进行排序。
	 * 
	 * 
	 * @param arr
	 * @param digit 最大数据的位数，比如100则输入3
	 * 
	 */
	public int[] sort(int[] arr, int digit) {
		if(arr==null){
			return null;
		}
		for (int i = 1; i <= Math.pow(10, digit - 1); i *= 10) {
			arr = countSort(arr, i);
		}
		return arr;
	}

	/**
	 * 算法要点：1、计数排序必须从后向前反向遍历原始数组，保证排序是稳定的。 2、排完序后将临时数组的值按正序替换原始数组。
	 * 
	 * @param arr
	 * @param radix
	 *            void
	 */
	private int[] countSort(int[] arr, int radix) {
		int radixArr[] = new int[10];
		for (int i = 0; i < arr.length; i++) {// 统计基数的个数
			int radixValue = getRadixValue(arr[i], radix);
			radixArr[radixValue] += 1;
		}
		for (int i = 1; i < 10; i++) {
			radixArr[i] += radixArr[i - 1];
		}
		int tempArray[] = new int[arr.length];
		for (int i = arr.length - 1; i >= 0; i--) {// 要从后向前遍历，这样才是稳定排序
			int radixValue = getRadixValue(arr[i], radix);
			tempArray[radixArr[radixValue] - 1] = arr[i];// 把arr[i]放入对应的位置(temp[radixValue]-1)上去
			radixArr[radixValue]--;
		}
		return tempArray;
	}

	private int getRadixValue(int arrValue, int radix) {
		return (arrValue / radix) % 10;
	}