共计 1143 个字符，预计需要花费 3 分钟才能阅读完成。
微信搜寻????「码农田小齐」，关注这个在纽约的程序媛，回复「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…
