对于输入 6,2,9,1,5,8 我得到 1,2,6,9,5,8。该算法是基于 https://gist.github.com/mycodeschool/9678029#file-mergesort_c-c-L28 编写的 请帮助我获取 1、2、5、6、8、9,因为输出也指出了这里的错误。提前致谢。
#include<iostream>
using namespace std;
void merge(int a[],int l[],int lc,int r[],int rc){
int i,j,k;
i=0;j=0;k=0;
while(i<lc && j<rc){
if(l[i]<r[j]){
a[k++]=l[i++];
}
else{
a[k++]=r[j++];
}
while(i<lc){
a[k++]=l[i++];
}
while(j<rc){
a[k++]=r[j++];
}
}
}
void mergesort(int a[],int n){
int mid;
if (n<2){
return;
}
mid=n/2;
int l[mid],r[n-mid];
for(int i=0;i<mid;i++){
l[i]=a[i];
}
for(int i=mid;i<n;i++){
r[i-mid]=a[i];
}
mergesort(l,mid);
mergesort(r,n-mid);
merge(a,l,mid,r,n-mid);
}
int main(){
int a[]={6,2,9,1,5,8};
int n=6;
mergesort(a,n);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
}
最佳答案
你的问题是这些循环
while(i<lc){
a[k++]=l[i++];
}
while(j<rc){
a[k++]=r[j++];
}
在这个循环内 while(i<lc && j<rc)
当您复制 a[]
的其余部分时,它们应该在它外面如果b[]
在 a[]
时完成有一些元素,对于 b[]
也是明智的这是整个合并功能
void merge(int a[],int l[],int lc,int r[],int rc)
{
int i,j,k;
i=0;
j=0;
k=0;
while(i<lc && j<rc)
{
if(l[i]<r[j])
{
a[k++]=l[i++];
}
else
{
a[k++]=r[j++];
}
}
while(i<lc)
{
a[k++]=l[i++];
}
while(j<rc)
{
a[k++]=r[j++];
}
}
关于c++ - 部分归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34644977/