彩虹排序 | 荷兰旗问题 _指针

微信搜索「码农田小齐」，关注这个在纽约的程序媛，回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源，么么哒～

文章插图
荷兰旗问题又称三色排序，或者彩虹排序，

文章插图
因为荷兰旗就三种颜色嘛，那这道题的问题就是给你三种颜色，按照给定的顺序排好。
当然了，题目的问法各种各样，有的给数字，有的给字母，但本质都是一样的。
比如给你一个只含有三个数字的数组：，
要求按照 1 2 3 的顺序排好，即：
（请不要真的去数数，认真你就输了）

文章插图

文章插图
还是用我们经典的「挡板法」。
在快排中，我们用了两个挡板把数组分成三个区域：
pivot
那么这里就要三个挡板，分成四个区域：
1, 2, 3, 未排序区间
具体说来，用 i, j, k 这三个指针分一下：
[0, i): 存 1
[i, j): 存 2
(k, array.-1]: 存 3
这里 j 放在未排序区间的左边和右边都行，但基本上大家都是放左边，所以我们也没必要“标新立异” 。
初始化：
i = 0;
j = 0;
k = array. - 1;
这样才能保证 1，2，3 的每个区间都为空。
我们通过观察指针 j 指向的元素来不断缩小未排序区间，直到为空。
例子：

文章插图
为了好看，排好序的元素我们用 RGB 三原色标示一下。
Step1.
指针 j 指向 1，而 1 应该放在 [0, i) 区间内，这里应该把指针 i 和指针 j 所指的元素交换一下，并且俩指针往前走。
虽然在这步看来是否交换没什么区别，但是如果 i 和 j 之间有元素，就有区别了，比如 Step7.