What is radix sort?

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

Intuitive expression: is to split each number according to its bits, and sort each corresponding bits by comparison until all the bits have gone through the sorting position

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

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

Letters: SDF can be split into S, D, and F by number of digits

chestnuts

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

First of all, we know that their largest value (839) has three digits (hundreds, tens, and ones), so we can sort and compare the corresponding digits of the sequence

First sort the units digit (the rightmost digit), and the result is

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

Then sort the ten-digit number (the middle number), and the result is

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

Then sort the hundreds (the rightmost number), and the result is

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

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

And you end up with a sorted sequence

So at this point somebody might ask, what if they have different digits? What if each element was a string of letters instead of numbers?

How to deal with different bits?

3, 200, 55, 220, 70

In general, we judge each digit from 0 to 9. If the digit is different, we need to determine in advance whether the element has a single digit, a ten digit, or a hundred digit. If not, it will rank before 0

The element is an English string, not a number?

Individual letters can also be sized, A-Z

The elements are English strings and numbers in the same way, but instead of the ones, tens, and hundreds, you can replace them with the 0th, 1st, and 2nd bits on the right

<img src=”https://noxussj.top:3000/30/1.png”></img>

Dynamic graph display

<img src=”https://noxussj.top:3000/30/2.gif”></img>

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 in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
  • [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/