What is the cardinality sort in java

This article mainly introduces what is the cardinality sort in java. It is very detailed and has a certain reference value. Friends who are interested must finish it!

Cardinality sort

Cardinal sorting (Radix Sort) is a non-comparative integer sorting algorithm, its principle is to cut integers into different digits, and then compare them according to each digit. The invention of cardinality can be traced back to Herman Holly's contribution to the punched card tabulator (Tabulation Machine) in 1887.

The cardinality sorting method uses Bucket, as the name implies, by comparing bits (individual, ten, hundred... In order to achieve the function of sorting, the elements to be sorted are assigned to 0,9 buckets. In some cases, the cardinality sorting method is more efficient than other comparative sorting methods.

Algorithm step

Unify all the values to be compared (positive integers) into the same digital length, with zeros before the numbers with shorter digits.

Start from the lowest level and sort it one by one.

From the lowest order to the highest order, the sequence becomes an ordered sequence.

Algorithm demonstration

GIF is a little slow to load in the animation. Please wait a moment ^ _ ^

Process interpretation of sorting animation

The cardinality sorting method can be LSD (Least sgnificant digital) or MSD (Most sgnificant digital).

LSD is used in this example

First create the 10 buckets numbered 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Traverse the entire sequence, check the number of digits, and store it in the corresponding numbered bucket in order.

For example, 321 digits are 1 and are stored in a numbered bucket.

The number 1 digit is 1, which is stored in the number 1 bucket and on top of 321.

After traversing the single digits of the whole sequence, after storing the numbers in the bucket, take out the numbers according to the numbering order, and take out the numbers that are put into the bucket first.

Then traverse the ten digits of the whole sequence in turn, and sort out the sequence according to the operation of the above single digits.

Traverse the hundred digits of the entire sequence in turn, and organize the sequence according to the operation of the single digits mentioned above

This completes the cardinality sorting.

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post the reference code of a variety of programming languages, all from the Internet.

Java code implementation

JavaScript code implementation

The above is all the content of the article "what is the cardinality sort in java". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!