快排-荷蘭國(guó)旗x
發(fā)布時(shí)間:2020-09-14 來(lái)源: 講話(huà)發(fā)言 點(diǎn)擊:
快排- 荷蘭國(guó)旗 在使用 partition-exchange 排序算法時(shí),如快速排序算法,我們會(huì)遇到一些問(wèn)題,比如重復(fù)元素太多,降低了效率,在每次遞歸中,左邊部分是空的(沒(méi)有元素比關(guān)鍵元素小),而右邊部分只能一個(gè)一個(gè)遞減移動(dòng)。結(jié)果導(dǎo)致耗費(fèi)了二次方時(shí)間來(lái)排序相等元素。這時(shí)我們可以多分一個(gè)區(qū),即,小于區(qū),等于區(qū),大于區(qū)。(傳統(tǒng)快排為小于區(qū)和大于區(qū))
下面我們通過(guò)一個(gè)經(jīng)典例題來(lái)練習(xí)這種思想。
荷蘭國(guó)旗問(wèn)題 ”荷蘭國(guó)旗難題“是計(jì)算機(jī)科學(xué)中的一個(gè)程序難題,它是由 Edsger Dijkstra 提出的。荷蘭國(guó)旗是由紅、白、藍(lán)三色組成的。
現(xiàn)在有若干個(gè)紅、白、藍(lán)三種顏色的球隨機(jī)排列成一條直線(xiàn),F(xiàn)在我們的任務(wù)是把這些球按照紅、白、藍(lán)排序。
樣例輸入 3
BBRRWBWRRR
RRRWWRWRB
RBRW
樣例輸出 RRRRRWWBBB
RRRRRWWWB
RRWB
思路:
現(xiàn)在我們的思路就是把未排序時(shí)前部和后部分別排在數(shù)組的前面和后面,那么中部自然就排好了。
設(shè)置兩個(gè)標(biāo)志位 head 指向數(shù)組開(kāi)頭,tail 指向數(shù)組末尾,now 從頭開(kāi)始遍歷:
(1)如果遍歷到的位置為 1,那么它一定是屬于前部,于是就和 head 交換值,然后head++,now++; (2)如果遍歷到的位置為 2,說(shuō)明屬于中部,now++; (3)如果遍歷到的位置為 3,說(shuō)明屬于后部,于是就和 tail 交換值,然而,如果此時(shí)交換后 now 指向的值屬于前部,那么就執(zhí)行(1),tail--; 廢話(huà)不多說(shuō),上代碼。
#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í)只要解題的話(huà)統(tǒng)計(jì)三個(gè)數(shù)量就好了,但是分三區(qū)的思想一定要有。
快排分三區(qū)以后降低了遞歸規(guī)模,避免了最差情況,性能得到改進(jìn)。
熱點(diǎn)文章閱讀