Algorithm idea: sort by single digits, ten digits... in turn. Each pos has an allocation process and a collection process. array[i][0] records the number of data in the i-th row.
package sorting;/** * Cardinality sort* Average O(d(n+r)), best O(d(n+r)), worst O(d(n+r)); space complexity O(n+r); stable; more complex* d is the number of digits, r is the number of linked lists after allocation* @author zeng * */public class RadixSort {//pos=1 represents single digits, pos=2 represents ten digits public static int getNumInPos(int num, int pos) {int tmp = 1;for (int i = 0; i < pos - 1; i++) {tmp *= 10;}return (num / tmp) % 10;}//Finding the maximum digit dpublic static int getMaxWeishu(int[] a) {int max = a[0];for (int i = 0; i < a.length; i++) {if (a[i] > max) max = a[i];}int tmp = 1, d = 1;while (true) {tmp *= 10;if (max / tmp != 0) {d++;} else break;} return d;}public static void radixSort(int[] a, int d) {int[][] array = new int[10][a.length + 1];for (int i = 0; i < 10; i++) {array[i][0] = 0;// array[i][0] record the number of data in row i }for (int pos = 1; pos <= d; pos++) {for (int i = 0; i < a.length; i++) {// Assignment process int row = getNumInPos(a[i], pos);int col = ++array[row][0];array[row][col] = a[i];}for (int row = 0, i = 0; row < 10; row++) {// Collection process for (int col = 1; col <= array[row][0]; col++) {a[i++] = array[row][col];}array[row][0] = 0;// Reset, you need to use the next pos }}}public static void main(String[] args) {int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };radixSort(a, getMaxWeishu(a));for (int i : a) System.out.print(i + " ");}}Pay attention to the running results:
Summarize
The above is all the content of this article about implementing cardinality sorting code for Java language implementation. I hope it will be helpful to everyone. Interested friends can continue to refer to other Java-related topics on this website. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!