C- 我的合并排序算法有什么问题？

Question

我编写了一个合并排序算法的代码，它有两个输入：位数和位数

而且我想打印按我的合并排序函数排序的数组。

但我只能看到运行时间错误.

我认为我的 Merge() 函数产生了运行时间错误。但是我在 Merge 函数中找不到 while 循环的 exception..

如何修复此错误并使运行合并排序正常运行？

这是我的代码

 #include <stdio.h>

void Merge(int *arr, int s, int e, int m);
void MergeSort(int *arr, int s, int e);

int main(void) {
    int N;
    scanf("%d", &N);
    int arr[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    MergeSort(arr, 0, N - 1);
    for (int i = 0; i < N; i++) {
        printf("%d", arr[i]);
    }
}

void MergeSort(int *arr, int s, int e) {
    printf("hi\n");
    int m;
    if (e - s > 0) {
        m = (s + e) / 2;
        MergeSort(arr, s, m);
        MergeSort(arr, m + 1, e);
        Merge(arr, s, e, m);
    } else {
        return;
    }
}

void Merge(int *arr, int s, int e, int m) {
    int arr_t[e - s + 1];
    int i = s, j = m + 1, idx = s;
    while (1) {
        if (i != m && j != s) {
            if (i <= m && arr[i] <= arr[j]) {
                arr_t[idx] = arr[i];
                i++;
                idx++;
            } else
            if (j <= e) {
                arr_t[idx] = arr[j];
                j++;
                idx++;
            }
        } else
        if (i == m && j != e) {
            arr_t[idx] = arr[j];
            j++;
            idx++;
        } else
        if (i != m && j == e) {
            arr_t[idx] = arr[i];
            i++;
            idx++;
        } else {
            if (arr[i] <= arr[j]) { 
                arr_t[idx] = arr[i];
                idx++;
                arr_t[idx] = arr[j];
            } else {
                arr_t[idx] = arr[j];
                idx++;
                arr_t[idx] = arr[i];
            }
            break;
        }
    }
    for (int k = s; k <= e; k++) {
        arr[k] = arr_t[k];
    }
}

Answer 1

您这部分代码的错误可能是由于：

正如@Some programmer dude 所述，您可能超出了数组之一的范围

您可以使用 while(i<=mid && j<=end) 而不是 while(1) 循环直到合并用完一个或两个部分

N 甚至不用在你的合并函数中使用这么多 else，你可以使用 while() 循环来简化你的 code.You 不应该在你的最后一个临时数组中附加两个值else 子句

甚至 if(i!=m && j!=s) 你的代码中的这个条件看起来有点奇怪。

所以我写了这个示例合并排序供您参考。希望这对您有所帮助！！

#include<stdio.h>
void merge(int a[],int start,int mid,int end){
int i=start,j=mid+1,k=0;
int temp[end-start+1];
while(i<=mid && j<=end){
    if(a[i]<a[j]){
        temp[k]=a[i];
        k+=1;
        i+=1;
    }
    else{
        temp[k]=a[j];
        k+=1;
        j+=1;
    }
}
while(i<=mid){
    temp[k]=a[i];
    i+=1;k+=1;
}
while(j<=end){
    temp[k]=a[j];
    j+=1;k+=1;
}
for(int i=end;i>=start;i--){
    a[i]=temp[--k];
}


}



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

}
}



void display(int a[],int n){
for(int i=0;i<n;i++)
printf("%d ",a[i]);

}



int main()

{
    int a[5]={5,4,6,2,1};
    int n=sizeof(a)/sizeof(a[0]);
    mergesort(a,0,n-1);
    display(a,n);
}

最坏情况下的时间复杂度为Ο(n log n)

C- 我的合并排序算法有什么问题？

C- What is the matter of my mergesort algorithm?

c

sorting

algorithm

mergesort

runtime-error