3. Radix Sort (기수 정렬)

public class RadixSort {
	static void radixSort(int nums[]) {
		int maxLen = getMaxLen(nums);
		List<Integer> cnt[];
		for(int radix = 0; radix <= maxLen; radix++) {
			cnt = new ArrayList[10];
			for (int i = 0; i < cnt.length; i++) cnt[i] = new ArrayList<>();
			for (int i = 0 ; i < nums.length; i++) 
				cnt[(int)(nums[i] % Math.pow(10, radix+1) / Math.pow(10, radix))].add(nums[i]);
			int idx = 0;
			for (List<Integer> list: cnt) if(list != null) for (int n : list) nums[idx++] = n;
		}
	}
	static int getMaxLen(int nums[]) {
		int max = 0;
		for (int n: nums) if (max < n) max = n;
		return (int)Math.log10(max)+1;
	}
}