C : Mergesort - what is the mistake? 错误输出(重复)

Question

我用 C 语言编写了这个“mergesort”。我认为在将元素复制回原始数组时存在错误。有人能帮我吗？

非常感谢。

enter code here

 /*************************** Merge sort ********************************/
  #include <stdio.h>

  void merge(int arr[], int start1, int end1, int start2, int end2)
  {
   int temp[100], beg1, beg2, i;

   beg1=start1;
   beg2=start2;
   i=0;

   while((beg1<=end1)&&(beg2<=end2))
   {
     if(arr[beg1]<arr[beg2])
      {
        temp[i++]=arr[beg1++];
      }
     else
      {
        temp[i++]=arr[beg2++];
      }
   }
   if(beg1<end1) {
       while(beg1<=end1) temp[i++]=arr[beg1++];
   }

  if(beg2<end2) {  
       while(beg2<=end2) temp[i++]=arr[beg2++];
  }

  i=0;
  for(beg1=start1; beg1<=end1; beg1++)
  {
      arr[beg1]=temp[i++];
  }
 for(beg1=start2; beg1<=end2; beg1++)
  {
      arr[beg1]=temp[i++];
  }
}

 void mergesort(int arr[], int beg, int end)
 {
   int mid;

   if(beg<end) {
      mid=(beg + end)/2;
      mergesort(arr, beg, mid);
      mergesort(arr, mid+1, end);
      merge(arr, beg, mid, mid+1, end);
   }
 }

 int main()
 {
   int i;
   int arr[]={34, 3, 10, 78, 4, 0, 14};
   mergesort(arr, 0, 6);

   printf("Here are the sorted elements:\n");

   for(i=0; i<6; i++){
      printf("%d\t",arr[i]);
   }
   printf("\n");
 }

Output:
  [root@dhcppc0 sorting]# gcc mergesort.c
  [root@dhcppc0 sorting]# ./a.out

     Here are the sorted elements:
          0       0       3       0       10      10

Answer 1

end1和 end2是有效的指数，所以我认为你不应该拥有那些 if声明在这里

if(beg1<end1) {
   while(beg1<=end1) temp[i++]=arr[beg1++];
}

if(beg2<end2) {  
   while(beg2<=end2) temp[i++]=arr[beg2++];
}

如果 beg1 会怎样== end1 ？

如果beg1<end1 ，您在 [beg1, end1] 范围内至少还有 2 个数组元素。如果只有一个，你也应该复制它。您应该让循环不受 if 语句的保护。将上面显示的代码更改为:

//if(beg1<end1) {
   while(beg1<=end1) temp[i++]=arr[beg1++];
//}

//if(beg2<end2) {  
   while(beg2<=end2) temp[i++]=arr[beg2++];
//}

附带说明一下，您的排序不稳定。要修复它，请更改此条件

if(arr[beg1]<arr[beg2])

到

if(!(arr[beg2]<arr[beg1]))