What is quicksort?

In a sequence of random to find out a number (called the base element), and then is smaller than benchmark element number on the left, larger than the base element number on the right, so it will be a divided into two sequences, and then according to the target sequence in the same way again divided into smaller subsequence, until can’t break down

chestnuts

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

Purple: The base element

Green: The number less than the base element

Yellow: The number larger than the base element

Algorithm description

Suppose a set of sequences is 6, 9, 2, 4, 5, 1, 8, 7

So let’s pick some random number (6).

Put the ones smaller than 6 on the left and the ones larger on the right

Results: 2, 4, 5, 1, 6, 9, 8, 7

You get 2 new sequences on the left (2, 4, 5, 1) and the right (6, 8, 7).

-------------------------------------------------

The sequence on the left is then split and the sequence on the right is not enumerated

Sequence 2, 4, 5, 1

Pick a random number (2) and continue with the judgment. Put the number smaller than 2 on the left and the number larger on the right

Results: 1, 2, 4, 5

I get 2 new sequences, left (1), right (4, 5).

-------------------------------------------------

Then you find that the sequence (1) on the left cannot be split, so you need to merge it up

The sequence on the right (4, 5) can be further split

Pick a random number (4) and continue with the judgment. Put the number smaller than 4 on the left and the number larger on the right

Results: 4, 5

I get the new sequence, left (4), right (5).

Then you find that the left sequence (4) and the right sequence (5) cannot be split, so you need to merge up

-------------------------------------------------

All elements are combined upwards to get the result

One, two, four, five, six, seven, eight

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

If you still don’t understand this diagram, then you haven’t understood quicksort. Take a pen and paper and try to sort it yourself

Comics: What is quicksort? (Full Version)

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/