Radix Sort
Cardinality sorting is also a non comparative sorting algorithm. It sorts each bit from the lowest order, with the complexity of O(kn), the length of the array, and k the largest number of digits in the array;
Cardinality sorting is to sort by the low order, then collect; then sort by the high order, then collect; and so on until the highest order. Sometimes some attributes have priority order. They are sorted by low priority first, and then by high priority. The last order is high priority first, high priority same low priority high priority first. Cardinality sorting is based on sorting separately and collecting separately, so it is stable.

Algorithm description
Gets the maximum number in the array and the number of digits;
arr is the original array, and each bit is taken from the lowest bit to form a radius array;
To count and sort the radix (using the characteristics of counting and sorting for small range number);

algorithm analysis
Best case: T(n) = O(n * k)
Worst case: T(n) = O(n * k)
Average: T(n) = O(n * k)
There are two ways to sort cardinality:
MSD sort from high order
LSD sort from low order

public static void radixSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

public static int maxbits(int[] arr) {
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < arr.length; i++) {
		max = Math.max(max, arr[i]);
	}
	int res = 0;
	while (max != 0) {
		res++;
		max /= 10;
	}
	return res;
}

public static void radixSort(int[] arr, int begin, int end, int digit) {
	final int radix = 10;
	int i = 0, j = 0;
	int[] count = new int[radix];
	int[] bucket = new int[end - begin + 1];
	for (int d = 1; d <= digit; d++) {
		for (i = 0; i < radix; i++) {
			count[i] = 0;
		}
		for (i = begin; i <= end; i++) {
			j = getDigit(arr[i], d);
			count[j]++;
		}
		for (i = 1; i < radix; i++) {
			count[i] = count[i] + count[i - 1];
		}
		for (i = end; i >= begin; i--) {
			j = getDigit(arr[i], d);
			bucket[count[j] - 1] = arr[i];
			count[j]--;
		}
		for (i = begin, j = 0; i <= end; i++, j++) {
			arr[i] = bucket[j];
		}
	}
}

public static int getDigit(int x, int d) {
	return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

Please refer to the blog for explanation of pictures and texts:
https://blog.csdn.net/hellozhxy/article/details/79911867