荷兰国旗

题目描述：

拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。

三色球和荷兰国旗

该问题本身是关于三色球排序和分类的，由荷兰科学家 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