重新排列红蓝绿3色球 荷兰国旗问题_要求重新排列red

Reorder Array of Red, Blue and Green balls（Dutch national flag problem）

一个有意思的问题：An array of some size contains Red, Blue and Green balls all mixed up randomly. like RGBBBRRGGG, where RGB is for Red, Green and Blue.

简单的说：有n个红蓝绿3种不同颜色的球，随机排成一列。现在需要使同种颜色的球排在一起并且按红蓝绿的顺序。（3中颜色简单的计为1 2 3）

这是经典的荷兰国旗问题（Dutch national flag problem，http://en.wikipedia.org/wiki/Dutch_national_flag_problem）。

1.当这个问题出现时，简单的方法是先扫描一遍序列，统计出各个颜色的个数，然后在数组中按各个颜色的个数填充各个颜色即可。

这个方法不错，但是需要2*n的时间。

2.这个问题类似于快速排序的数的交换。将比蓝色小的球放在左边，比蓝色大的球放在右边。 其中关键的是，出现了与蓝色相等的求的处理，例如：1 2 1 2 2 3 2 3的情况.

有一种处理方法，使用头尾两个指针，同时使用一个变量，记录第一次出现2颜色的位置（只需n步操作）࿱