c - 合并两个已排序数组的困难

Question

我编写了这个函数，用于在合并排序实现中合并两个已排序的数组，但我总是得到错误的输出。

void merge(int array[],int l,int m,int r)
{
   int i,j,k,n1,n2;
   n1=m-l+1;
   n2=r-m;
   int left[n1],right[n2];
   for(i=0;i<n1;i++)
   left[i]=array[l+i]
   for(i=0;i<n2;i++)
   right[i]=array[m+i+1]
   i=0; j=0;
   for(k=l;k<r;k++)
   {
       if(left[i]<=right[j])
       {
         array[k]=left[i];
         i+=1;
       }
        else
       {
         array[k]=right[j];
         j+=1;
       }
}

示例输入:4 6 3 1 2

输出:1 2 3 0 2

我不知道哪里出了问题。我遵循 Cormen 中给出的归并排序算法。谁能帮帮我吗？

Answer 1

改变

for(k=l;k<r;k++)
{
    if(left[i]<=right[j])
    {
      array[k]=left[i];
      i+=1;
    }
     else
    {
      array[k]=right[j];
      j+=1;
    }
}

至

for(k=l;k<=r;k++){
    if(j>=n2 || i<n1 && left[i] <= right[j])
        array[k] = left[i++];
    else
        array[k] = right[j++];
}