Rainbow sorting | Dutch flag problem

WeChat search 「 Yard farmland, Xiao Qi 」, Focus on this program in New York , reply 「01-05」 You can get a selection of computer books 、 Personal writing notes 、 Big factory surface 、 Interview materials and other resources , mua ～

The Dutch flag problem is also called tricolor order , Or rainbow sort ,

Because the Dutch flag has three colors , The problem with this question is to give you three colors , Arrange in the given order .

Yes, of course , There are various ways to ask questions , Some give numbers , Some give letters , But the essence is the same .

For example, give you an array of three numbers ：312312312231111122113,
The requirements are as follows 1 2 3 Put it in order , namely ：
111111111222222222223333333333
（ Please don't really count , You lose when you get serious ）

Or use our classic 「 Baffle method 」.

In the express line , We used two baffles to divide the array into three areas ：

<= pivot; Unordered range ;> pivot

So here's three baffles , Divided into four areas ：

1, 2, 3, Unordered range

Partition

say concretely , use i, j, k These three hands are divided ：
[0, i): save 1
[i, j): save 2

(k, array.length-1]: save 3

here j Put it to the left and right of unsorted intervals , But basically we put it on the left , So we don't have to “ new in order to be different ”.

initialization ：

i = 0;
j = 0;
k = array.length - 1;
In this way, we can guarantee 1,2,3 Each interval of is empty .

We go through Watch the pointer j Pointing elements To keep narrowing the unsorted range , Until it's empty .

Example ：1232312

To look good , The ordered elements we use RGB Three primary colors to mark .

Step1.

The pointer j Point to 1, and 1 Should be placed in [0, i) Within the interval ,
The pointer should be put here i And a pointer j Exchange the elements , And the two hands go forward .

Although at this point it doesn't make any difference whether it's a swap or not , But if i and j There are elements in between , There's a difference , such as Step7.

Step2.

The pointer j Point to 2, and 2 Should be placed in [i, j) Within the interval , therefore j++.

Step3.

The pointer j Point to 3, and 3 Should be placed in
(k, array.length-1] Within the interval , So here
j and k Point to the element exchange , also k--.

Notice that you can't j-- 了 , Because I haven't seen the new elements yet , I don't know what it is .

Step4.

The pointer j Point to 2, Same as Step2, Move the pointer directly j that will do .

Step5.

Keep moving the pointer j.

Step6.

Same as Step3.

Step7.

This step is obvious ,
because 1 Should be placed in [0,i) Section , So here's the pointer i,j Exchange the elements you point to , also i++, j++.

So the unsorted interval is empty , We're in line ～

Time complexity

This algorithm bottle neck That's it while loop In the , Every cycle is O(1), The total is O(n).

Spatial complexity

O(1)

If you like this article , Remember to leave me a like message ～ Your support and recognition , It's the biggest driving force of my creation , See you in the next article ！

This is Qi , New York program , Lifelong learners , Every night 9 spot , Let's meet you in the cloud study room ！

See my... For more dry articles Github: https://github.com/xiaoqi6666...