Cardinality sorting (detailed illustration)

One 、 What is cardinal sort

（1） The value of each bit through the key value , Assign the elements to be sorted to some buckets , To achieve the function of sorting
（2） Radix sort is a sort of stability , Cardinal ranking method is a stable ranking method with high efficiency
（3） Cardinality sorting is an extension of bucket sorting

Two 、 Realization principle

         Compare the values to be compared （ Natural number ） Uniform to the same digit length , A shorter digit is zeroed . then , Let's start at the lowest point , Sort them one at a time . In this way, from the lowest ranking to the completion of the highest ranking , The sequence becomes an ordered sequence .

3、 ... and 、 Implementation steps

（1） Determine the maximum number of elements in the array （MAX）（ Determine the number of rounds performed ）

（2） establish 0~9 A barrel （ At the bottom of the bucket is the queue ）, Because all digital elements are made of 0~9 Ten numbers of

（3） Judge the bits of each element in turn , Ten to MAX position , Put it into the corresponding bucket , Out of the team , Save to the original array ; straight

          to MAX Round end output array .

（4） The specific implementation steps are shown in the figure below

Four 、 Code implementation

import java.util.LinkedList;

public class Radix {

	public static void main(String[] args) {

		int[] arr = { 23, 1, 4, 9, 98, 132, 42 };

		sort(arr);

	}

	public static void sort(int[] arr) {
		// 1. look for   classification - collect   The number of rounds （ The length of the maximum ）
		int radix = getRadix(arr);
		// 2. Creating buckets  list Collection of all barrels   Each barrel is LinkedList Use it as a queue 
		LinkedList<Integer>[] list = new LinkedList[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = new LinkedList<>();
		}
		// 3. Start   classification - collect 
		for (int r = 1; r <= radix; r++) {
			//  The classification process 
			for (int i = 0; i < arr.length; i++) {
				list[getIndex(arr[i], r)].offer(arr[i]);
			}
			int index = 0; //  Traverse arr Original array 
			//  The process of collecting 
			for (int i = 0; i < list.length; i++) {
				while (!list[i].isEmpty()) {
					arr[index++] = list[i].poll();
				}
			}

		}

		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}

	}

	private static int getIndex(int num, int r) {
		int ret = 0;
		for (int i = 1; i <= r; i++) {
			ret = num % 10;
			num /= 10;
		}
		return ret;
	}

	private static int getRadix(int[] arr) {
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		return (max + "").length();
	}

}