时间：2014.08.07
地点：基地
----------------------------------------------------------------------------------
一、题目描写叙述
现有红白蓝三个不同颜色的小球，乱序排列在一起。又一次排列这些小球。使得红白蓝三色的同颜色的球在一起。
这个问题之即荷兰国旗问题，将红白蓝三色小球想象成条状物。有序排列后正好组成荷兰国旗。
例如以下图所看到的：
----------------------------------------------------------------------------------
二、思路
2.1方法一：排序
若是把颜色与数值相应起来。事实上是个简单的排序问题，仅仅只是元素取值仅仅含3个。且有反复，最好还是设为0 1 2 ，
于是採用各种排序都可解决。时间复杂度对于各种排序方法相应的时间复杂度。
2.2方法二：划分
将元素划分成三个部分。思路：
2.2.1 设置三个指针begin current end，begin current初始化指向数组首元素，end初始化指向数组尾元素
2.2.2 检查current指向的值，为 0 ：则与begin交换值。然后current begin均后移一个位置
为1 ：则begin不动。current后移一个位置
为2：则与end交换值。然后current后移一个位置，end前移一个位置
2.2.3反复上述过程，当current>end时停止，注意这里的条件不能够取等于（比方在序列中假设存在连续的 2 0。恰好current指向2。end指向0。则交换后为0 2，而这之前可能还有1，此时还不能终止反复过程。时间复杂符为O(n)
代码例如以下：
//荷兰国旗问题2014.08.07
#include<iostream>
#include<vector>
#include<algorithm>
void Partition(std::vector<int>& vec)
{
auto begin = vec.begin();
auto end = vec.end() - 1;
auto cursor = begin;
while (cursor <= end)
{
if (0 == *cursor)
{
std::swap(*cursor, *begin);
++begin;
++cursor;
}
else if (1 == *cursor)
++cursor;
else
{
std::swap(*cursor, *end);
--end;
}
}
}
int main()
{
std::vector<int> vec{0, 1, 1,1,2,0,2,1,0, 2, 0, 2 };
Partition(vec);
for (auto element : vec)
std::cout << element << ' ';
std::cout << std::endl;
}
这样的方法总的目标是将元素分为三部分。0放最前。所以遇到0，得和前面交换位置，遇到2得和后面交换位置，而遇到1，begin保存不动。cursor向前演进，如此可保证0在前面部分，2在后面部分，而1夹在中间。
3.统计法：
逐步检查数组，统计 0 1 2出现的次数，然后再向数组按顺序写入相应次数的值。也可到达目的。时间复杂度也是O(n)。但相比划分法多会多一个常量因子，由于这里需两次遍历数组。