RadixSort.java

importjava.io.*;
importjava.util.*;
classRadixSort {
staticintgetMax(int[] arr, intn)
 {
intmx = arr[0];
for (inti = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
returnmx;
 }
staticvoidcountSort(int[] arr, intn, intexp)
 {
int[] output = newint[n]; // output array
inti;
int[] count = newint[10];
Arrays.fill(count, 0);
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
 }
for (i = 0; i < n; i++)
arr[i] = output[i];
 }
staticvoidradixsort(int[] arr, intn)
 {
intm = getMax(arr, n);
for (intexp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
 }
staticvoidprint(int[] arr, intn)
 {
for (inti = 0; i < n; i++)
System.out.print(arr[i] + " ");
 }
publicstaticvoidmain(String[] args)
 {
Scannersc=newScanner(System.in);
intn=sc.nextInt();
int[] arr=newint[n];
for(inti=0;i<n;i++)
arr[i]=sc.nextInt();
radixsort(arr, n);
print(arr, n);
 }
}