1.题目描述
现有红白蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫</span>荷兰国旗</span>，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。</span>如下图所示：</span></span>
2.问题分析：
这个问题我们可以将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在[0,1]的区域里，由于三色小球之间数量的比不同（此处假设1:2:2），可能前部为[0,0.2)，中部为[0.2,0.6)，后部为[0.6,1]。我们的思路如下：将前部和后部各排在数组的前边和后边，中部自然就排好了。具体的：
设置两个标志位begin和end分别指向这个数组的开始和末尾，然后用一个标志位current从头开始进行遍历：
1）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。
2）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前进。
3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向后退1。
3.代码演示：
1. `#include <iostream>`
2. `using namespace std;`
3. `void exch(int& a,int &b)`
4. `{`
5. ` int t = a;`
6. ` a = b;`
7. ` b = t;`
8. `}`
9. `void HFlag(int a[],int n)`
10. `{`
11. ` int begin,current,end;`
12. ` begin = 0; //指?向ò0组×é`
13. ` current = 1; //指?向ò1组×é`
14. ` end = n-1; //指?向ò2组×é`
15. ` while(current != n)`
16. ` {`
17. ` if(a[current] == 0)`
18. ` {`
19. ` exch(a[current],a[begin]);`
20. ` current++;`
21. ` begin++;`
22. ` }`
23. ` if(a[current] == 1)`
24. ` {`
25. ` current++;`
26. ` }`
27. ` if(a[current] == 2)`
28. ` {`
29. ` exch(a[current],a[end]);`
30. ` end--;`
31. ` current++;`
32. ` }`
33. ` }`
34. `}`
35. `int main()`
36. `{`
37. ` int a[10];`
38. ` for(int i=0;i<10;i++)`
39. ` a[i] = rand()%3;`
40. ` HFlag(a,10);`
41. ` for(int i=0;i<10;i++)`
42. ` cout << a[i] <<" ";`
43. ` system("pause");`
44. ` return 0;`
45. `}`
1. `运行结果：`
2. `2211210012`
3. `0011112222`
4. `请按任意键继续...`
[来自为知笔记(Wiz)](http://www.wiz.cn/i/c09d0bb5 "来自为知笔记(Wiz)")
