荷兰国旗
题目描述：
拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。
三色球和荷兰国旗
该问题本身是关于三色球排序和分类的，由荷兰科学家 Dijkstra 提出。由于问题中的三色小球有序排列后正好分为三类， Dijkstra 就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。
下面是问题的正规描述： 现有 n 个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。
为了方便讨论，用数字 0 表示红球，用数字 1 表示白球，用数字 2 表示蓝球，所以最后要求的数字排列是 0，...，1，...，2，... 。
分析和解法：
初看此题，貌似除了暴力解决并无好的办法，但是可以联想到刚才用过的快排算法。快速排序依托于一个 partition 分治过程，在每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的部分，那么我们可以借鉴一下。
解法一：
通过前面的分析得知，这个问题类似快排中 partition 过程，只是需要用到三个指针：一个前指针 begin，一个中指针 current ，一个后指针 end， current 指针遍历整个数组序列，当
- current 指针所指元素为 0 时，与 begin 指针所指的元素交换，而后 current++，begin++ ；
- current 指针所指元素为 1 时，不做任何交换（即球不动），而后 current++ ；
- current 指针所指元素为 2 时，与 end 指针所指的元素交换，而后， current 指针不动，end-- 。
源代码如下：
#include <iostream>
using namespace std;
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int a[100];
int n = 0;
while(cin.peek() != '\n') cin >> a[n++];
int *begin, *current, *end;
begin = &a[0];
current = &a[0];
end = &a[n - 1];
while(current <= end)
{
if (*current == 0)
{
Swap(*current, *begin);
current++;
begin++;
}
else if (*current == 1)
current++;
else
{
Swap(*current, *end);
end--;
}
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
return 0;
}
分析：时间复杂度为 O（n）。
特别注意：
当然如果不限制空间的话，我们还有其他更简单的方法。
参考资料：《编程之法》The Art of Programming By July
