微信搜索??「碼農田小齊」，關注這個在紐約的程式媛，回復「01-05」可以獲取計算機精選書籍、個人刷題筆記、大廠面經、面試資料等資源，么么噠～
荷蘭旗問題又稱三色排序，或者彩虹排序，
因為荷蘭旗就三種顏色嘛，那這道題的問題就是給你三種顏色，按照給定的順序排好，
當然了，題目的問法各種各樣，有的給數字，有的給字母，但本質都是一樣的，
比如給你一個只含有三個數字的陣列：312312312231111122113，
要求按照 1 2 3 的順序排好，即：
111111111222222222223333333333
（請不要真的去數數，認真你就輸了）
還是用我們經典的「擋板法」，
在快排中，我們用了兩個擋板把陣列分成三個區域：
<= pivot；未排序區間；> pivot
那么這里就要三個擋板，分成四個區域：
1, 2, 3, 未排序區間
Partition
具體說來，用 i, j, k 這三個指標分一下：
[0, i): 存 1
[i, j): 存 2
(k, array.length-1]: 存 3
這里 j 放在未排序區間的左邊和右邊都行，但基本上大家都是放左邊，所以我們也沒必要“標新立異”，
初始化：
i = 0;
j = 0;
k = array.length - 1;
這樣才能保證 1，2，3 的每個區間都為空，
我們通過觀察指標 j 指向的元素來不斷縮小未排序區間，直到為空，
例子：1232312
為了好看，排好序的元素我們用 RGB 三原色標示一下，
Step1.
指標 j 指向 1，而 1 應該放在 [0, i) 區間內， 這里應該把指標 i 和指標 j 所指的元素交換一下，并且倆指標往前走，
雖然在這步看來是否交換沒什么區別，但是如果 i 和 j 之間有元素，就有區別了，比如 Step7.
Step2.
指標 j 指向 2，而 2 應該放在 [i, j) 區間內，所以 j++.
Step3.
指標 j 指向 3，而 3 應該放在
(k, array.length-1] 區間內，所以這里
j 和 k 指向的元素交換一下，并且 k--.
注意這里就不能 j-- 了，因為新換回來的元素還沒瞧呢，不知道它是幾，
Step4.
指標 j 指向 2，同 Step2，直接移動指標 j 即可，
Step5.
繼續移動指標 j，
Step6.
同 Step3.
Step7.
這一步就很明顯看出來了，
由于 1 應該放在 [0,i) 區間，所以這里把指標 i，j 所指向的元素交換一下，并且 i++, j++.
這樣未排序區間為空，我們就排好了～
時間復雜度
這個演算法的 bottle neck 就在這個 while loop 里了，每次回圈是 O(1)，總共是 O(n).
空間復雜度
O(1)
如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！
我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，云自習室里不見不散！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/207978.html
標籤：其他
上一篇：初入docker
下一篇：golang的go mod使用