import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
System.out.println("Before: " + Arrays.toString(array));
sort1(array);
System.out.println("After: " + Arrays.toString(array));
array = new int[]{-5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
sort2(array);
System.out.println("After: " + Arrays.toString(array));
}
public static void sort1(int[] arr) {
// This method doesn't support negative values
if (arr.length <= 1) {
return;
}
int max = 0;
// sort out the max element
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// Bucket numbers, here we adopt 10 buckets, also known as decimal base.
// More buckets, more efficient, but more memory space.
int bucketNum = 10;
int maxLen = 1;
// sort out the length of max element
while (max / bucketNum > 0) {
maxLen++;
max = max / bucketNum;
}
int[][] buckets = new int[bucketNum][arr.length];
// base is determined by allocated bucket number
int base = bucketNum;
for (int i = 0; i < maxLen; i++) {
// keep track of the size of each bucket for later insertion
int[] bktSize = new int[bucketNum];
// allocate the elements to corresponding buckets according to the ith digit counting from tail
for (int j = 0; j < arr.length; j++) {
// find out the jth digit counting from the tail
// base=10, arr[j]=172; arr[j] % base=2, base/10=1; 2/1=2
int bktId = (arr[j] % base) / (base / bucketNum);
// Even element arr[x] and arr[y] share same bucket, arr[x] will be put into the bucket first
// if arr[x]'s (j-1)th digit is larger than arr[y]'s because of previous round sorting on (j-1)th digit.
buckets[bktId][bktSize[bktId]] = arr[j];
bktSize[bktId]++;
}
int count = 0;
// collect the elements in order which are sorted by the ith digit
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktSize[b]; p++) {
arr[count++] = buckets[b][p];
}
}
base *= bucketNum;
}
}
public static void sort2(int[] arr) {
// This supports negative values, just double the quantity of buckets.
if (arr.length <= 1) {
return;
}
int max = 0;
// sort out the max element
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// Bucket numbers, here we adopt 10 buckets, also known as decimal base.
// More buckets, more efficient, but more memory space.
int bucketNum = 10;
int maxLen = 1;
// sort out the length of max element
while (max / bucketNum > 0) {
maxLen++;
max = max / bucketNum;
}
int[][] buckets = new int[bucketNum * 2][arr.length];
// base is determined by allocated bucket number
int base = bucketNum;
for (int i = 0; i < maxLen; i++) {
// keep track of the size of each bucket for later insertion
int[] bktSize = new int[bucketNum * 2];
// allocate the elements to corresponding buckets according to the ith digit counting from tail
for (int j = 0; j < arr.length; j++) {
// find out the jth digit counting from the tail
// base=10, arr[j]=172; arr[j] % base=2, base/10=1; 2/1=2
int bktId = (arr[j] % base) / (base / bucketNum) + bucketNum;
// Even element arr[x] and arr[y] share same bucket, arr[x] will be put into the bucket first
// if arr[x]'s (j-1)th digit is larger than arr[y]'s because of previous round sorting on (j-1)th digit.
buckets[bktId][bktSize[bktId]] = arr[j];
bktSize[bktId]++;
}
int count = 0;
// collect the elements in order which are sorted by the ith digit
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktSize[b]; p++) {
arr[count++] = buckets[b][p];
}
}
base *= bucketNum;
}
}
}