import java.util.ArrayList;
import java.util.List;
public class HelloWorld {
public static void main(String[] args) {
int[] nums = {61,92,123522,41234,223,817,31,8,5124};
List<Integer> list = new ArrayList<>();
for (int i: nums){
list.add(i);
}
RadixSort radixSort = new RadixSort(nums);
int[] orginNums = radixSort.getOrginNums();
int[] sortedNums = radixSort.getSortedNums();
for (int i: orginNums){
System.out.print(i + " ");
}
System.out.println();
for (int i: sortedNums){
System.out.print(i + " ");
}
}
}
class RadixSort {
private int[] orginNums;
private int[] sortedNums;
private static final int DIGIT_SIZE = 10;
private int size;
public RadixSort(int[] nums){
orginNums = nums;
size = nums.length;
radixSort(nums);
}
private void radixSort(int[] nums){
int digitCount = getDigitCount(nums);
List<List<Integer>> digitList = initDigitList();
int[] tempNums = copyNums(nums);
for (int i = 0; i < digitCount; i++){
for (int j = 0; j < tempNums.length; j++){
int digit = getDigit(tempNums[j], i);
digitList.get(digit).add(tempNums[j]);
}
getThisDigitSort(digitList, tempNums);
}
this.sortedNums = tempNums;
}
private List<List<Integer>> initDigitList() {
List<List<Integer>> digitList = new ArrayList<>();
for (int i = 0; i < DIGIT_SIZE; i++) {
digitList.add(new ArrayList<>());
}
return digitList;
}
private int[] copyNums(int[] nums) {
int[] tempNums = new int[nums.length];
for (int i = 0; i < nums.length; i++){
tempNums[i] = nums[i];
}
return tempNums;
}
private void getThisDigitSort(List<List<Integer>> digitList, int[] tempNums) {
int tempIndex =0;
for (int j = 0; j < DIGIT_SIZE; j++){
List<Integer> list = digitList.get(j);
while (list.size() > 0){
Integer num = list.remove(0);
tempNums[tempIndex] = num;
tempIndex++;
}
}
}
private int getDigitCount(int[] nums){
int digitCount = 0;
int max = nums[0];
for (int i: nums){
if (max < i){
max = i;
}
}
while (max > 0){
digitCount++;
max /= 10;
}
return digitCount;
}
private int getDigit(int num, int digitIndex){
int digit = 0;
while (digitIndex > 0){
num /= 10;
digitIndex--;
}
return num % 10;
}
public int[] getOrginNums() {
return orginNums;
}
public int[] getSortedNums() {
return sortedNums;
}
public int getSize() {
return size;
}
}