c++ - 部分归并排序

Question

对于输入 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]<<" ";
}
}

Answer 1

你的问题是这些循环

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++];
    }
}