分治算法中排序的完整代码
问题描述
- 精选答案
-
问题之处:
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<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
void MERGE(vector<int> &A,int p,int q,int r)
{
int i,j,k=0;
int n1=q-p+1;
int n2=r-q;
vector<int> L((n1+1),0),R((n2+1),0);
for(vector<int>::size_type i=0;i!=n1;++i)
L[i]=A[p+i-1];
for(vector<int>::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<int> &A,int p,int r)
{
int q;
if(p<r){
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<int> 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<int>::iterator ix=A.begin();ix!=A.end();++ix)
cout<<*ix<<' ';
system(
"pause
");
return 0;
}
猜你喜欢内容
-
简单网:构建全网教育数据枢纽,让知识检索化繁为...
简单网:构建全网教育数据枢纽,让知识检索化繁为“简”回答数有0条优质答案参考
-
去三亚有什么好玩的地方
去三亚有什么好玩的地方回答数有1条优质答案参考
-
石狮一日游必去景点推荐
石狮一日游必去景点推荐回答数有1条优质答案参考
-
电气工程师的证书考取条件是什么
电气工程师的证书考取条件是什么回答数有1条优质答案参考
-
房地产估价师的具体报考条件有啥
房地产估价师的具体报考条件有啥回答数有1条优质答案参考
-
房产经纪人的工作内容具体包含什么
房产经纪人的工作内容具体包含什么回答数有1条优质答案参考
-
学习小提琴都有哪些难点
学习小提琴都有哪些难点回答数有1条优质答案参考
-
企业行政管理证书的含金量怎么样
企业行政管理证书的含金量怎么样回答数有1条优质答案参考
-
初学者要怎么入门小提琴
初学者要怎么入门小提琴回答数有1条优质答案参考
-
报考珠宝鉴定师要啥条件
报考珠宝鉴定师要啥条件回答数有1条优质答案参考
















