189 8069 5689
上方的图片便是一个荷兰国旗，从图中我们可以很清楚的看出它的特点,它有三个区域组成，即红，白，蓝。
好，现在我们的问题出来了。现在我们面前有一张桌子，桌子上整齐的摆放着红色，白色，蓝色三种线条，但他们的顺序是凌乱的。
要求是：用一个算法把这些线条挑出来重新摆放顺序，最后的结果就像上图的荷兰国旗，红色在上，白色在中间，蓝色在最下面。
另外，要求在O(n)的复杂度下，使移动次数最少。
算法分析如下：
荷兰国旗问题其实是一个排序问题。可以将红，白，蓝3种颜色分别用数字0、1和2表示，并使用一个数组来存储它们。将相同颜色
的线条归为一类就相当于将数组中的数组按大小进行排序，只不过数组里存储的数值只有3种而已。其解题的基本策略是遍历两个颜色区域，
如果颜色条不属于所在区域，则交换一个属于该区域的颜色条。这样，每一次都是必要的交换，从而实现最少交换次数。
代码如下：
#include
using namespace std;
const int N=10;
int flag[N]; //国旗颜色条数组
int pre[N]; //记录该白条的前白条位置
int split1; //区域分割1
int split2; //区域分割2
int blue_red; //红条在蓝色区域的标记
int white_red; //红条在白色区域的标记
int counts = 0;
void out()
{
for (int i=0;i
cout<
cout<
void swap(int& x,int& y)
{
int temp=x;
x=y;
y=temp;
counts++;
}
void work()
{
for (int i=0;i
if (flag[i]!=0) //如果不属于该区域
{
if(blue_red>=split2)
{
swap(flag[i],flag[blue_red]);
blue_red = pre[blue_red];
}
else{
swap(flag[i],flag[white_red]);
white_red = pre[white_red];
}
}
}
int b=N-1; //白、蓝区域
for ( i=split1;i
if (flag[i] != 1)
{
while (flag[b]==2) b--;
swap(flag[i],flag[b]);
b--;
}
}
}
//初始化
void init()
{
int red_num = 0; //统计红色条数
int white_num = 0; //统计白色条数
int preI = -1;
for (int i=0;i
flag[i] = rand()%3;
if (flag[i]==0)
{
red_num++;
pre[i] = preI;
preI=i;
}
else
if (flag[i]==1)
{
white_num++;
}
}
//将国旗分成3个颜色区域：
//0~split-1(红)，split1~split2-1(白),split2~N-1(蓝）
split1=red_num;
split2=red_num+white_num;
blue_red=preI;
i=split2-1;
while (flag[i] !=0) i--;
white_red = i;
}
int main()
{
init();
cout<<"原始:"<
work();
cout<<"移动"<
return 0;
}