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...
