合并排序程序错误

Question

我正在做一个C合并排序程序，但我得到了一些意想不到的输出。 任何人都可以找出程序中的错误？

#include<stdio.h> 

    int array[100],n; 
    void merge(int l,int m,int h); 
    void mergesort(int start,int end); 
    main(){ 
    int i; 
    printf("Enter Size: "); 
    scanf("%d",&n); 
    for(i=0;i<n;i++){ 
     scanf("%d",&array[i]);  
    } 
    mergesort(0, n-1); 
    for(i=0;i<n;i++){ 
     printf("%d\n",array[i]);   
     } 
    } 

    void mergesort(int start,int end){ 
    int mid; 
    if(start<end){ 
     mid=(start+end)/2; 
     mergesort(start,mid); 
     mergesort(mid+1,end); 
     merge(start,mid,end); 
     } 
    } 

    void merge(int start,int mid,int end){ 
    int i,j,k; 
    int a1[100],a2[100]; 

    for(k=0,i=start;i<=mid;i++,k++){ 
     a1[k]=array[i]; 
    } 
    for(k=0,j=i;j<=end;j++,k++){ 
     a2[k]=array[j]; 
    } 
    a1[mid]=999; 
    a2[j]=999; 
    i=0;j=0; 
    for(k=start; k <=end; k++) 
    { 
     if(a1[i]<=a2[j]) 
      array[k]=a1[i++]; 
     else 
      array[k]=a2[j++]; 
    } 
} 

输出：

Enter Size: 5 
1 2 3 2 3 
2 
2 
3 
3 
-1818025592 

对于较大的阵列，输出更多的加扰。我认为merge（）函数有一个错误。

Answer 1

您正在终止您的a1和a2阵列在错误的位置。

尝试改变：

for(k=0,i=start;i<=mid;i++,k++){ 
    a1[k]=array[i]; 
} 
for(k=0,j=i;j<=end;j++,k++){ 
    a2[k]=array[j]; 
} 
a1[mid]=999; 
a2[j]=999; 

到

for(k=0,i=start;i<=mid;i++,k++){ 
    a1[k]=array[i]; 
} 
a1[k]=999; 
for(k=0,j=i;j<=end;j++,k++){ 
    a2[k]=array[j]; 
} 
a2[k]=999; 

Answer 2

当您创建临时数组：

for (k = 0, i = start; i <= mid; i++, k++) { 
    a1[k] = array[i]; 
} 
a1[i] = 999; 

你把警戒值，并在最后一个高值。但i是原始array的索引。您必须使用k，临时数组a1的指标：

for (k = 0, i = start; i <= mid; i++, k++) { 
    a1[k] = array[i]; 
} 
a1[k] = 999; 

即使如此，与k和i双重控制结构是笨拙的。而且没有必要猜测一个很高的数字; <limits.h>对大多数类型的最小值和最大值定义的常量：

k = 0; 
for (i = start; i <= mid; i++) { 
    a1[k++] = array[i]; 
} 
a1[k] = INT_MAX; 

在这里，你增加k当一个项目被追加。即使分配有条件地发生，即不是在所有迭代中，这都是有效的。

最后，我会建议使用独占的上限。这是用C表达范围的自然方式。然后，mid将是左数组的独占上限和右数组的下限。

Answer 3

我已经解决了它
一个[中间+ 1] = 999
一个[K] = 999