现有红白蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。如下图所示：
初看此题，我们貌似除了暴力解决并无好的办法，但联想到我们所熟知的快速排序算法呢？我们知道，快速排序时基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：
- 分解：A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1...r]，使得A[p...q-1] <= A[q] <= A[q+1...r]
- 解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]排序。
- 合并。
也就是说，快速排序的主要思想便是依托于一个partition分治过程，每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的序列，继而递归排序完整个数组。
如下伪代码所示：
快速排序算法的关键是PARTITION过程，它对A[p...r]进行就地重排：
PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
7 exchange A[i + 1] <-> A[r]
8 return i + 1
继而递归完成整个排序过程：
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r) //关键
3 QUICKSORT(A, p, q - 1)
4 QUICKSORT(A, q + 1, r)
举个例子如下：i指向数组头部前一个位置，j指向数组头部元素，j在前，i在后，双双从左向右移动。
① j 指向元素2时，i 也指向元素2，2与2互换不变
i p/j
2 8 7 1 3 5 6 4(主元)
② 于是j 继续后移，直到指向了1，1 <= 4，于是i++，i 指向8，故j 所指元素1 与 i 所指元素8 位置互换：
i j
2 1 7 8 3 5 6 4
③ j 继续后移，指到了元素3,3 <= 4，于是同样i++，i 指向7，故j 所指元素3 与 i 所指元素7 位置互换：
i j
2 1 3 8 7 5 6 4
④ j 一路后移，没有再碰到比主元4小的元素：
i j
2 1 3 8 7 5 6 4
⑤ 最后，A[i + 1] <-> A[r]，即8与4交换，所以，数组最终变成了如下形式：
2 1 3 4 7 5 6 8
ok，至此快速排序第一趟完成。就这样，4把整个数组分成了俩部分，2 1 3,7 5 6 8，再递归对这俩部分分别进行排序。
全部过程可以参看此文：快速排序算法，或看下我以前在学校里画的图：
而我们面对的问题是，重新排列使得所有球排列成三个不同颜色的球，是否可以设定三个指针，借鉴partition过程呢？
通过前面的分析得知，这个问题类似快排中partition过程，只是需要用到三个指针：一个前指针begin，一个中指针current，一个后指针end，current指针遍历整个数组序列，当
- current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++ ；
- current指针所指元素为1时，不做任何交换（即球不动），而后current++ ；
- current指针所指元素为2时，与end指针所指的元素交换，而后，current指针不动，end-- 。
为什么上述第3点中，current指针所指元素为2时，与end指针所指元素交换之后，current指针不能动呢？因为第三步中current指针所指元素与end指针所指元素交换之前，如果end指针之前指的元素是0，那么与current指针所指元素交换之后，current指针此刻所指的元素是0，此时，current指针能动么？不能动，因为如上述第1点所述，如果current指针所指的元素是0，还得与begin指针所指的元素交换。
ok，说这么多，你可能不甚明了，直接引用下gnuhpc的图，就一目了然了：
参考代码如下：
//引用自gnuhpc
while( current<=end )
{
if( array[current] ==0 )
{
swap(array[current],array[begin]);
current++;
begin++;
}
else if( array[current] == 1 )
{
current++;
}
else //When array[current] =2
{
swap(array[current],array[end]);
end--;
}
} 本章完。