算法分析之三色旗算法

一条绳子挂红白蓝三种颜色的旗子，且排列无序，现用程序把三种旗子同色归类，顺序为蓝-白-红，每次只能交换2面旗子，采用最少步骤完成。

算法描述：只需把红色和蓝色的旗子进行交换，红旗和篮旗都就位后，白旗自然就位。

1) 如果白旗所在位置的元素是白旗，表示该位置的元素应该在此，将white++，接着处理下一个旗子；

2) 如果white所在位置的元素是蓝旗，表示需将蓝旗与blue变量所在位置的元素对调，然后使blue++、white++,处理下一个旗子；

3) 如果white所在位置的元素是红旗，表示需要将红旗与red变量的元素对调，然后将red--,继续处理下一旗子。

namespace section10_threeFlags{
int count;
char color[]="rwbwwbrbwr";
int blue,white,red;
//exchange variable a and b
void swap(char * a, char *b){
    char temp;
    int i;
    temp = *a;
    *a=*b;
    *b=temp;
    count++;
    printf("the %dth order exchanged
",count);
    for(i=0;i<(int)strlen(color);i++){
            printf("%c ",color[i]);
    }
    printf("
");
}
void threeFlags(){
    while(color[white]=='b'){
        blue++;
        white++;
    }
    while(color[red]=='r'){
        red--;
    }
    while(white<=red){
        if(color[white]=='r'){
            swap(&color[white],&color[red]);
            red--;
            while(color[red]=='r'){
                red--;
            }
        }
        while(color[white]=='w'){
            white++;
        }
        if(color[white]=='b'){
            swap(&color[white],&color[blue]);
            blue++;
            white++;
        }
    }
}
void runThreeFlags(){
    int i,len;
    blue=white=0;
    len=strlen(color);
    red=len-1;
    count=0;
    printf("The original flags' array are as follows:
 ");
    for(i=0;i<len;i++){
        printf("%c ",color[i]);
    }
    printf("
");
    threeFlags();
    printf("The last result :
");
    for(i=0;i<len;i++){
        printf("%c ",color[i]);
    }
    printf("
");
}