算法之三色旗_三色旗算法

三色旗，顾名思义，就是三种颜色的旗子，红白蓝，乱序地寄在一根绳子上，现在需要按照顺序排列，分别是前面旗子为蓝色，中间为白色，后面为红色。每次只能调换两个旗子，如何在移动次数最少的情况下，排序成功。

本案例算法其实算是经典的排序问题，通过不断移动对比来进行排序，如下图所示：

假设排好序后，那么a代表头指针对应蓝色，b代表移动指针对应白色，c是尾指针对应红色；

核心思想是通过b的移动，并分别判断颜色，交换旗子，最终达到排序的目的。

如果b是白色，那么直接后移一位；（白色本身就应该在中间所以不处理）

如果b是蓝色，那么将a，b互换，同时a，b分别后移一位（蓝色需要换到头上，所以与a换，互换后，a，b各后移一位）

如果b是红色，那么将c，b互换，并且c前移一位（红色需要放到尾部，所以需要和c换，同时互换后c确认已经是红色，c直接前移）

基本程序如下：

#include<stdio.h>
#include<string.h>
#define BLUE 'b'
#define WHRITE 'w'
#define RED   'r'
#define swap(x,y) { char temp;   \
               temp = color[x];  \
               color[x] = color[y];  \
               color[y] = temp;    \
               }
int main()
{
   char color[]={'r','w','r','b','b','r','w','w','r','b','r','w','\0' };
   int wFlags = 0;
   int bFlags = 0;
   int rFlags = strlen(color)-1;
   int i;
   for(i=0;i<strlen(color);i++)
    printf("%c ",color[i]);
   printf("\n");
   while(wFlags <= rFlags){
    if(color[wFlags] == WHRITE) {
       wFlags++;
    } else if(color[wFlags] == BLUE) {
       swap(wFlags,bFlags);
       wFlags++;
       bFlags++;
    } else {
       swap(wFlags, rFlags);
       rFlags--;
    }
   }
   for(i=0;i<strlen(color);i++)
     printf("%c ",color[i]);
   return 0;
}