分治演算法中排序的完整程式碼？使用者7956859634438762019-05-12 05:09:16

問題之處：

1．陣列要傳遞引用，否則不會被改變。

2．程式碼要加括號：

for（int k=p-1；k！=r；++k） {

if（L［i］<=R［j］）{

A［k］=L［i］；

++i；

}

else if（L［i］>R［j］）{

A［k］=R［j］；

++j；

}

}

－－－－－－－－－－－－－－－－－－－

完整程式碼：

#include

#include

#include

using namespace std；

void MERGE（vector &A，int p，int q，int r）

{

int i，j，k=0；

int n1=q-p+1；

int n2=r-q；

vector L（（n1+1），0），R（（n2+1），0）；

for（vector：：size_type i=0；i！=n1；++i）

L［i］=A［p+i-1］；

for（vector：：size_type j=0；j！=n2；++j）

R［j］=A［q+j］；

L［n1］=88888；

R［n2］=88888；

i=0；

j=0；

for（int k=p-1；k！=r；++k） {

if（L［i］<=R［j］）{

A［k］=L［i］；

++i；

}

else if（L［i］>R［j］）{

A［k］=R［j］；

++j；

}

}

}

void MERGE_SORT（vector &A，int p，int r）

{

int q；

if（p

if（（r-p+1） % 2==0）q=（r+p+1）/2-1；

if（（r-p+1） % 2==1）q=（r+p）/2；

MERGE_SORT（A，p，q）；

MERGE_SORT（A，q+1，r）；

MERGE（A，p，q，r）；

}

}

int main（）

{

int val；

vector A；

//while（cin>>val）

// A。push_back（val）；

A。push_back（9）；

A。push_back（8）；

A。push_back（2）；

A。push_back（4）；

A。push_back（3）；

MERGE_SORT（A，1，A。size（））；

for（vector：：iterator ix=A。begin（）；ix！=A。end（）；++ix）

cout<<*ix<<‘ ’；

system（“pause”）；

return 0；

}