快排- 荷蘭國旗 在使用 partition-exchange 排序算法時，如快速排序算法，我們會遇到一些問題，比如重復元素太多，降低了效率，在每次遞歸中，左邊部分是空的(沒有元素比關鍵元素小)，而右邊部分只能一個一個遞減移動。結果導致耗費了二次方時間來排序相等元素。這時我們可以多分一個區(qū)，即，小于區(qū)，等于區(qū)，大于區(qū)。（傳統(tǒng)快排為小于區(qū)和大于區(qū)）

　 下面我們通過一個經(jīng)典例題來練習這種思想。

　荷蘭國旗問題 ”荷蘭國旗難題“是計算機科學中的一個程序難題，它是由 Edsger Dijkstra 提出的。荷蘭國旗是由紅、白、藍三色組成的。

　現(xiàn)在有若干個紅、白、藍三種顏色的球隨機排列成一條直線。現(xiàn)在我們的任務是把這些球按照紅、白、藍排序。

　樣例輸入 3

　BBRRWBWRRR

　RRRWWRWRB

　RBRW

　樣例輸出 RRRRRWWBBB

　RRRRRWWWB

　RRWB

　思路：

　現(xiàn)在我們的思路就是把未排序時前部和后部分別排在數(shù)組的前面和后面，那么中部自然就排好了。

　設置兩個標志位 head 指向數(shù)組開頭，tail 指向數(shù)組末尾，now 從頭開始遍歷：

　(1)如果遍歷到的位置為 1，那么它一定是屬于前部，于是就和 head 交換值，然后head++，now++； (2)如果遍歷到的位置為 2，說明屬于中部，now++； (3)如果遍歷到的位置為 3，說明屬于后部，于是就和 tail 交換值，然而，如果此時交換后 now 指向的值屬于前部，那么就執(zhí)行(1)，tail--； 廢話不多說，上代碼。

　#include<iostream>

　#include<algorithm>

　using namespace std;

　const int maxn = 100 + 5;

　int n;

　string str;

　int main(){

　cin>>n;

　while(n--){

　cin>>str;

　int len=str.size();

　int now=0,ans=0;

　int head=0,tail=len-1;

　while(now<=tail){

　if(str[now]=="R"){

　swap(str[head],str[now]);

　head++;

　now++;

　}

　else if(str[now]=="W"){

　now++;

　}

　else{

　swap(str[now],str[tail]);

　tail--;

　}

　}

　cout<<str<<endl;

　}return 0;

　}

　其實只要解題的話統(tǒng)計三個數(shù)量就好了，但是分三區(qū)的思想一定要有。

　快排分三區(qū)以后降低了遞歸規(guī)模，避免了最差情況，性能得到改進。

相關熱詞搜索：荷蘭 國旗