荷蘭國旗
題目描述：
拿破侖席卷歐洲大陸之后，代表自由，平等刁岸，博愛的豎色三色旗也風(fēng)靡一時。荷蘭國旗就是一面三色旗（只不過是橫向的）她我，自上而下為紅白藍(lán)三色虹曙。
該問題本身是關(guān)于三色球排序和分類的，由荷蘭科學(xué)家 Dijkstra 提出番舆。由于問題中的三色小球有序排列后正好分為三類酝碳， Dijkstra 就想象成他母國的國旗，于是問題也就被命名為荷蘭旗問題（Dutch National Flag Problem）合蔽。
下面是問題的正規(guī)描述： 現(xiàn)有 n 個紅白藍(lán)三種不同顏色的小球击敌，亂序排列在一起介返，請通過兩兩交換任意兩個球拴事，使得從左至右，依次是一些紅球圣蝎、一些白球刃宵、一些藍(lán)球。
為了方便討論徘公，用數(shù)字 0 表示紅球牲证，用數(shù)字 1 表示白球，用數(shù)字 2 表示藍(lán)球关面，所以最后要求的數(shù)字排列是 0坦袍，...，1等太，...捂齐，2，... 缩抡。
分析和解法：
初看此題奠宜，貌似除了暴力解決并無好的辦法，但是可以聯(lián)想到剛才用過的快排算法瞻想⊙拐妫快速排序依托于一個 partition 分治過程，在每一趟排序的過程中蘑险，選取的主元都會把整個數(shù)組排列成一大一小的部分滴肿，那么我們可以借鑒一下。
解法一：
通過前面的分析得知佃迄，這個問題類似快排中 partition 過程泼差，只是需要用到三個指針：一個前指針 begin竿音，一個中指針 current ，一個后指針 end拴驮， current 指針遍歷整個數(shù)組序列春瞬，當(dāng)
- current 指針?biāo)冈貫?0 時，與 begin 指針?biāo)傅脑亟粨Q套啤，而后 current++宽气，begin++ ；
- current 指針?biāo)冈貫?1 時潜沦，不做任何交換（即球不動）萄涯，而后 current++ ；
- current 指針?biāo)冈貫?2 時唆鸡，與 end 指針?biāo)傅脑亟粨Q涝影，而后， current 指針不動争占，end-- 燃逻。
源代碼如下：
#include <iostream>
using namespace std;
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int a[100];
int n = 0;
while(cin.peek() != '\n') cin >> a[n++];
int *begin, *current, *end;
begin = &a[0];
current = &a[0];
end = &a[n - 1];
while(current <= end)
{
if (*current == 0)
{
Swap(*current, *begin);
current++;
begin++;
}
else if (*current == 1)
current++;
else
{
Swap(*current, *end);
end--;
}
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
return 0;
}
分析：時間復(fù)雜度為 O（n）。
特別注意：
當(dāng)然如果不限制空間的話臂痕，我們還有其他更簡單的方法伯襟。
參考資料：《編程之法》The Art of Programming By July
