三色旗问题

三色旗问题：
假设有一个数组，它有n个元素，每一个不外乎是红，白，蓝3种颜色之一的代号，就用R，W，B代表。这些元素在数组中并没有依同样颜色的元素排在一起的方式来排列，请写一个程序把这些元素排成所有蓝色在前，接着是白色，最后是红色的排列方式，不过在写程序时要满足下面的条件：
（1）不能用额外的内存，换句话说，只能在数组之内用互换的方式完成。
（2）互换两个元素的动作要越少越好。
（3）对于每一个元素而言，测试它是红，是白，还是蓝的工作每种颜色最多只能做一次测试。
在这个条件下，请写一个最快的程序。
----------------解决方案--------------------------------------------------------

这倒是个值得考虑的问题，有难度．
我有空再想想。

----------------解决方案--------------------------------------------------------
#include "Stdio.h"
#include "Conio.h"
#define SWAP(x,y) { char temp; \
temp=x; \
x=y; \
y=temp; \
}
int main(void)
{
char color[]="wbrwbbrrwwrwbrrwww";
int i=0,j=0,k=strlen(color)-1;
while(color[j]=='b')
i++,j++;
while(color[k]=='r')
k--;
while(j<k)
{
if(color[j]=='r')
{
SWAP(color[j],color[k]);k--;
while(color[k]=='r')
k--;
}
while(color[j]=='w')
j++;
if(color[j]=='b')
{
SWAP(color[j],color[i]);
i++,j++;
}
}
puts(color);
getch();
return 0;
}
这个应该算符合要求，但不知道是不是最简的，

[此贴子已经被作者于2006-8-31 22:20:13编辑过]

----------------解决方案--------------------------------------------------------

有一个条件不符合！
那就是：
（3）对于每一个元素而言，测试它是红，是白，还是蓝的工作每种颜色最多只能做一次测试。

----------------解决方案--------------------------------------------------------
引用
while(j<k)
{
if(color[j]=='r')
{
SWAP(color[j],color[k]);　/*加个k--;就符合要求了*/
while(color[k]=='r') //红色的j，k是同一个元素，被测试两次是否为红，有一次是没用
k--;
}
那只是我为简化写法而写的，倒让您误会了，
----------------解决方案--------------------------------------------------------
呵呵，写的不错，我再看看还有没有问题！
----------------解决方案--------------------------------------------------------
那您再帮我看看，我把那个改了．呵呵，谢了。

[此贴子已经被作者于2006-8-31 22:20:42编辑过]

----------------解决方案--------------------------------------------------------

找到一个：
当char color[]="brbrwrwbbrbwb";时答案不正确。

----------------解决方案--------------------------------------------------------

恩，谢谢。寝室马上停电了，我得下了，晚上我再改改．呵呵。

----------------解决方案--------------------------------------------------------
#include "Stdio.h"
#include "Conio.h"
#define SWAP(x,y) { char temp; \
temp=x; \
x=y; \
y=temp; \
}
int main(void)
{
char color[]="brbrwrwbbrbwb";
int i=0,j=0,k=strlen(color)-1;
while(color[j]=='b')
i++,j++;
while(color[k]=='r')
k--;
while(j<=k)
{
if(color[j]=='r')
{
SWAP(color[j],color[k]);k--;
while(color[k]=='r')
k--;
}
while(color[j]=='w')
j++;
if(color[j]=='b')
{
SWAP(color[j],color[i]);
i++,j++;
}
}
puts(color);
getch();
return 0;
}
加个＝号
----------------解决方案--------------------------------------------------------