What is radix sort?

Basic idea: Radix sort is sorted by low order first, then collect; Then sort it in high order and collect it again; And so on up to the highest place

Intuitive expression: it is to split each number according to its number of digits, and compare and sort each corresponding number of digits until all the digits have been sorted again

The most important thing about basic sorting is the number of bits

Numbers: 832 can be divided into units, tens and hundreds by the number of digits

Letter: SDF can be divided into s, D, and F by the number of bits

chestnuts

Suppose we have a set of sequences: 329, 457, 657, 839, 436, 720, 355

First of all, we know that their maximum value (839) has 3 digits (hundreds, tens, units), so we can sort and compare the corresponding digits of this set of sequences

The units digit (the rightmost number) is sorted first, and the result is

720, 355, 436, 457, 657, 329, 839

The ten digits (the middle number) are then sorted and the result is

720, 329, 436, 839, 355, 457-657

The hundreds (the rightmost number) are then sorted and the result is

329, 355, 436, 457, 657, 720, 839

Each bit is sorted and compared separately, so the traversal is over.

You end up with a sorted sequence

And then at this point someone will say, well, what if they have different digits? What if each element was a string of letters instead of numbers?

How do we deal with different bits?

3, 200, 55, 220, 70

Generally, we judge each digit from 0 to 9, if the digit is different, then we need to judge in advance whether the element has the ones digit, the tens digit, the hundreds digit, if not, then the row is in front of 0

Is the element a string, not a number?

Individual letters can be sized, a-Z

The same is true for strings and numbers, but instead of units, tens, and hundreds, we can replace them with 0, 1, and 2 on the right

Dynamic graph display

Comics: What is Radix Sort?

additional

  • This article is published through multiple platforms of “we media” and will not be maintained after publication. If you have any objection to the content, you can discuss it on GitHub below

  • Continuous maintenance/update 500+ github.com/noxussj/Int…

  • 3D city modeling using three.js (Zhuhai