问题描述：现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右的球依次为红球、白球、蓝球。这个问题之所以叫做荷兰国旗，是因为将红白蓝三色的小球弄成条状物，并有序排列后正好组成荷兰国旗。
解题方法1：蛮力求解
解题方法2：为了讨论方便用数字0表示红色球，用数字1表示白色球，用数字2表示蓝色球，所以最后的排序就是0…1…2…
快速排序基于划分过程，选取主元间整个数组划分为两个子数组。是否可以借鉴划分过程设定三个指针完成一次遍历完成重新排列，使得所有的球排列成三类不同颜色的球？
（1）设置三个指针： 一个前指针begin，一个中指针current，一个后指针。
current指针遍历整个数组序列
（2）当current指针所指元素为0时，与begin指针所指的元素进行交换（只是交换元素不交换指针位置），然后current++,begin++
（3）当current指针所指元素为1时，不做任何交换（即不移动球），然后current++
（4）当current指针所指元素为2时，与end指针所指的元素进行交换（同样直交换元素不交换指针位置），然后current指针位置不动，end–
参考代码：
#include <bits/stdc++.h>using namespace std;void FranceFlag( int *a , int n )
{
int begin = ;
int current = ;
int end = n - ;
while( current <= end )
{
if( a[current] == )
{
swap( a[begin] , a[current] );
begin++;
current++;
}
else if( a[current] == )
{
current++;
}
else
{
swap( a[end], a[current] );
end--;
}
}
for( int i = ; i < n ; i ++ )
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[] = {,,,,,,,,,};
FranceFlag(a,);
}
GCC运行结果：
举一反三：
给定一个只有R、G、B三个字符的字符串，请重新排列该字符串中的字符，使得新字符串中的各个字符的排序顺序为：R在前，G在中，B在后。要求空间复杂度为O(1)且只能遍历一次字符串
转载请注明：www.cnblogs.com/zpfbuaa
