假設有一根繩子，上面有一些紅、白、藍色的旗子。起初旗子的順序是任意的，現在要求用最少的次數移動這些旗子，使得它們按照藍、白、紅的順序排列。注意只能在繩子上操作，并且一次只能調換兩個旗子。
分析：其實要移動旗子得到要求的結果很簡單，但是需要注意的是需要移動最少的次數這個限制條件。
網上的一種解法：
從繩子開頭進行，遇到藍色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：
只是要讓移動次數最少的話，就要有些技巧：
如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。
如果W部份為藍色，則B與W的元素對調，而B與W必須各+1，表示兩個群組都多了一個元素。
如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。
注意B、W、R并不是三色旗的個數，它們只是一個移動的指標；什幺時候移動結束呢？一開始時未處理的R指標會是等于旗子的總數，當R的索引數減至少于W的索引數時，表示接下來的旗子就都是紅色了，此時就可以結束移動，如下所示：
該程序選自：經典算法大全 老奔整理 Email: [ben0133@163.com](#)
~~~
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED 'r'
using namespace std;
int times = 0;
char color[] = {'r', 'w', 'b', 'w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'};
//#define SWAP(x, y) { char temp; \
// temp = color[x]; \
// color[x] = color[y]; \
// color[y] = temp; }
void printArr()
{
cout<<"第"<<times<<"次的排序結果為：";
for (int i =0; i<strlen(color);i++)
{
cout<<color[i];
}
cout<<endl;
}
void SWAP(int x, int y)
{
char temp;
temp = color[x];
color[x] = color[y];
color[y] = temp;
times++;
printArr();
};
int main() {
int wFlag = 0;
int bFlag = 0;
int rFlag = strlen(color) - 1;
int i;
cout<<"移動前：";
for(i = 0; i < strlen(color); i++)
printf("%c", color[i]);
printf("\n");
while(wFlag <= rFlag) {
if(color[wFlag] == WHITE)
wFlag++;
else if(color[wFlag] == BLUE) {
SWAP(bFlag, wFlag);
bFlag++; wFlag++;
}
else {
while(wFlag < rFlag && color[rFlag] == RED)
rFlag--;
SWAP(rFlag, wFlag);
rFlag--;
}
}
cout<<"移動后："<<endl;
for(i = 0; i < strlen(color); i++)
printf("%c", color[i]);
printf("\n");
cout<<"cost time is :"<<times<<endl;
system("pause");
return 0;
}
~~~
程序執行結果為：
注意觀察打印出來的結果，可以發現有一些冗余的移動，導致移動次數比較大改進的解法如下：進行兩趟遍歷，首先對于成對的順序相反的紅色和藍色旗子，交互其位置其次對前后的藍色和紅色旗幟進行整理，使其聚集到一起
~~~
//三色旗問題改進
//可大體分為三步，首先交換b和r的位置，直到所有b都在r之前；
//然后整理前半部分的b，使其都靠前
//最后整理后半部分的r，使其都靠后
#include <iostream>
using namespace std;
int g_nExchangeNum = 0;
char szFlagInput[1024] = {'r','w','b','w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'};
//char szFlagInput[1024] = {"rwwwwrbbbrrwrrbbrrrbbbbwwwbrr"};
void ExchangeColor(char *pSour, char *pDes)
{
char szTemp;
g_nExchangeNum++;
szTemp = *pSour;
*pSour = *pDes;
*pDes = szTemp;
cout<<"第"<<g_nExchangeNum<<"次移動，結果為： "<<szFlagInput<<endl;
}
//r和b互換
void ScanFrist()
{
char *pBlue = szFlagInput;
char *pRed = szFlagInput + strlen(szFlagInput) - 1;
while (pRed > pBlue)
{
while (pBlue < szFlagInput + strlen(szFlagInput) - 1 && *pBlue != 'r' )
{
pBlue++;
}
while(pRed > szFlagInput && *pRed!= 'b')
pRed--;
if(pRed > pBlue)
ExchangeColor(pBlue, pRed);
}
}
//藍色旗幟調整完畢后，調整紅色旗幟
void ScanSecond()
{
char *pWhite = NULL;
char *pBlue = NULL;
char *pRed = NULL;
//調整藍色旗幟
pRed = szFlagInput ;
while (pRed < szFlagInput+ strlen(szFlagInput))
{
if (*pRed != 'r')
{
pRed++;
}
else
break;
}
if (pRed != szFlagInput) //有藍色的旗幟
{
if(pRed == szFlagInput + strlen(szFlagInput) )
pBlue = szFlagInput + strlen(szFlagInput) -1;
else
pBlue = pRed - 1;
pWhite = szFlagInput;
while(pWhite < pBlue)
{
while(pWhite< szFlagInput + strlen(szFlagInput) - 1 && *pWhite != 'w')
pWhite++;
while(pBlue > szFlagInput && *pBlue!= 'b')
pBlue--;
if (pWhite < pBlue)
{
ExchangeColor(pWhite,pBlue);
}
}
}
//調整紅色旗幟
if(pRed == szFlagInput + strlen(szFlagInput))
return;
pWhite = szFlagInput + strlen(szFlagInput) -1;
while (pWhite > pRed)
{
while(pRed< szFlagInput + strlen(szFlagInput) - 1 && *pRed != 'r')
pRed++;
while( pWhite> szFlagInput && *pWhite!= 'w')
pWhite--;
if (pWhite > pRed)
{
ExchangeColor(pWhite,pRed);
}
}
}
int main()
{
cout<<"未移動前結果為： "<<szFlagInput<<endl;
ScanFrist();
ScanSecond();
cout<<"the color list of the result is :"<<endl;
cout<<" "<<szFlagInput<<endl;
cout<<"總共的交換次數為："<<g_nExchangeNum<<endl;
system("pause");
return 1;
}
~~~
程序執行結果為3，無冗余移動步驟：
