c++ 中的归并排序算法
我有以下代码
#include <iostream>
using namespace std;
void merge(int c[],int a[],int n,int b[],int m){
for (int i=0,j=0,k=0;k<n+m;k++){
if (i==n) { c[k]=b[j++]; continue;}
if (j==m ){ c[k]=a[i++];continue;}
c[k]=(a[i]<b[j])? a[i++]:b[j++];
}
}
void mergesort(int a[],int b[],int l,int r){
if (l>r) return ;
int m=(l+r)/2;
mergesort(b,a,l,m);
mergesort(b,a,m+1,r);
merge(a+l,b+l,m-l+1,b+m+1,r-m);
}
int main(){
int a[]={12,4,2,5,3,6,7,8,10,11};
const int n=sizeof(a)/sizeof(int);
int b[n];
mergesort(a,b,0,n-1);
for (int i=0;i<n;i++){
cout<<b[i]<< " ";
}
return 0;
}
，但这里有这样的警告，
1>------ Rebuild All started: Project: mergesort, Configuration: Debug Win32 ------
1> mergesort.cpp
1>d:\c++_algorithms\mergesort\mergesort\mergesort.cpp(24): warning C4717: 'mergesort' : recursive on all control paths, function will cause runtime stack overflow
1> mergesort.vcxproj -> D:\c++_algorithms\mergesort\Debug\mergesort.exe
========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========
请帮助我修复它
，我已经更新了我的代码
i have following code
#include <iostream>
using namespace std;
void merge(int c[],int a[],int n,int b[],int m){
for (int i=0,j=0,k=0;k<n+m;k++){
if (i==n) { c[k]=b[j++]; continue;}
if (j==m ){ c[k]=a[i++];continue;}
c[k]=(a[i]<b[j])? a[i++]:b[j++];
}
}
void mergesort(int a[],int b[],int l,int r){
if (l>r) return ;
int m=(l+r)/2;
mergesort(b,a,l,m);
mergesort(b,a,m+1,r);
merge(a+l,b+l,m-l+1,b+m+1,r-m);
}
int main(){
int a[]={12,4,2,5,3,6,7,8,10,11};
const int n=sizeof(a)/sizeof(int);
int b[n];
mergesort(a,b,0,n-1);
for (int i=0;i<n;i++){
cout<<b[i]<< " ";
}
return 0;
}
but here is such warning
1>------ Rebuild All started: Project: mergesort, Configuration: Debug Win32 ------
1> mergesort.cpp
1>d:\c++_algorithms\mergesort\mergesort\mergesort.cpp(24): warning C4717: 'mergesort' : recursive on all control paths, function will cause runtime stack overflow
1> mergesort.vcxproj -> D:\c++_algorithms\mergesort\Debug\mergesort.exe
========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========
please help me to fix it
i have updated my code
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
mergesort() 需要检测是否被要求对长度为 1 的列表进行排序，如果是，则立即返回。另外，我可能是错的，但我认为对 merge() 的调用在对 mergesort() 的递归调用之后。
mergesort() needs to detect whether it's been asked to sort a list of length one, and if so, return immediately. Also, I could be wrong, but I think the call to merge() goes after the recursive calls to mergesort().
您的递归调用应该有一个终止条件，以便递归调用会在某个时刻结束。
我认为在 mergesort 函数的开头添加以下条件可以解决问题：
Your recursive call should have a terminating condition so that the recursive calls would end at some point.
I think adding the following condition at the beginning of your mergesort function solves the problem:
您需要有一个基本情况，这可能意味着您应该检查要排序的数组的大小是否为 =1，如果是，则返回该特定元素本身。
在代码中，这意味着检查类似的内容
，而且从逻辑上讲，在对两个子数组进行排序后应该调用 merge 。
You need to have a base case, which probably means that you should check whether the size of the array you are sorting is =1, and if it is, you return that particular element itself.
In code, this would mean checking something like
Also, logically, merge should be called after you have sorted the two sub-arrays.
您需要在 mergeSort 函数中指定基本情况！而且，在 mergeSort 算法中，对 merge 的调用是在对左右子数组的递归调用之后进行的
you need to specify a base case in your mergeSort function! and also, in the mergeSort algorithm, the call to merge comes after the recursive call to the left and right subarrays