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

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

　荷蘭國(guó)旗問題 ”荷蘭國(guó)旗難題“是計(jì)算機(jī)科學(xué)中的一個(gè)程序難題，它是由 Edsger Dijkstra 提出的。荷蘭國(guó)旗是由紅、白、藍(lán)三色組成的。

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

　樣例輸入 3

　BBRRWBWRRR

　RRRWWRWRB

　RBRW

　樣例輸出 RRRRRWWBBB

　RRRRRWWWB

　RRWB

　思路：

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

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

　(1)如果遍歷到的位置為 1，那么它一定是屬于前部，于是就和 head 交換值，然后head++，now++； (2)如果遍歷到的位置為 2，說明屬于中部，now++； (3)如果遍歷到的位置為 3，說明屬于后部，于是就和 tail 交換值，然而，如果此時(shí)交換后 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;

　}

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

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

相關(guān)熱詞搜索：荷蘭 國(guó)旗