Merge Sort Error : Segmentation Fault

Question

我遇到错误 Segmentation Fault:11，请帮忙。变量信息：(s:start, e:end, m:mid, n:array)，测试样本数组 n[] = {4,3,2,1}。 a1 和 a2 是临时数组。我猜 m:mid 的计算和传递是有问题的。

#include <stdio.h>

void merge(int s, int e, int m, int n[]) {
    int l1 = m - s;
    int l2 = e - m + 1;
    int a1[l1];
    int a2[l2];
    for (int i = 0; i < l1; i++) {
        a1[i] = n[s + i];
    }
    for (int j = 0; j < l2; j++) {
        a2[j] = n[s + m + j];
    }

    int i = 0, j = 0; 
    for (int k = 0; k < l1 + l2; k++) {
        if (a1[i] <= a2[j] && i != l1 && j != l2) {
            n[k] = a1[i];
            i++;
        } else if (a2[j] <= a1[i] && i != l1 && j != l2) {
            n[k] = a2[j];
            j++;
        } else if (j == l2 && i != l1) {
            n[k] = a1[i];
            i++;
        } else if(i == l1 && j != l2) {
            n[k] = a2[j];
            j++;
        }
    }
}

void mergeSort(int s, int e, int n[]) {
    if (s < e) {
        int m = (e - s) / 2;
        mergeSort(s, m - 1, n);
        mergeSort(m, e, n);
        merge(s, e, m, n);
    }
}

int main(void) {
    int n[] = { 4, 3, 2, 1 };
    int r = 4;
    mergeSort(0, r - 1, n);

    for(int i = 0; i < r; i++) {
        printf("%i\n", n[i]);
    }
}

Answer 1

我已经在几个地方修改了您的代码。尝试使用调试器或笔和纸来了解幕后发生的事情。

void merge(int s, int e, int m, int n[]){

    int l1 = m-s + 1;
    int l2 = e - m;
    int a1[l1];
    int a2[l2];
    for(int i = 0; i < l1; i++){
        a1[i] = n[s+i];
    }
    for(int j = 0; j < l2; j++){
        a2[j] = n[m+j + 1];

    }


    int i = 0, j = 0; 
    for(int k = 0; k < l1+l2; k++){
        if(a1[i] <= a2[j] && i != l1 && j != l2){
            n[k] = a1[i];
            i++;
        }else if(a2[j] <= a1[i] && i != l1 && j != l2){
            n[k] = a2[j];
            j++;
        }else if(j == l2 && i != l1){
            n[k] = a1[i];
            i++;
        }else if(i == l1 && j != l2){
            n[k] = a2[j];
            j++;
        }
    }

}
void mergeSort(int s, int e, int n[]){
        if(s<e){
            int m = s + (e-s)/2;
            mergeSort(s, m, n);
            mergeSort(m + 1, e, n);
            merge(s,e,m, n);
}

我想你会没事的。

Answer 2

我认为你有一个 stack overflow 问题，因为无限递归调用。看

void mergeSort(int s, int e, int n[]){
    if(s<e){
        int m = (e-s)/2;
        mergeSort(s, m-1, n);
        mergeSort(m, e, n);
        merge(s,e,m, n);
    }

}

您传递 s 和 e 的这些值：

s e function
-------------
0 3 mergeSort
    0 0 mergeSort -> end
    1 3 mergeSort
        0 0 mergeSort -> end
        1 3 mergeSort
            ... (infinite calls)

然后堆栈不断增长，同时调用新函数，直到最后超过最大可能大小，从而导致 SEGFAULT。

Answer 3

中间元素 m 的计算是假的：您从 s 得到 m 的偏移量，而不是它在数组中的索引。

这是更正后的版本：

void mergeSort(int s, int e, int n[]) {
    if (s < e) {
        int m = s + (e - s + 1) / 2;
        mergeSort(s, m - 1, n);
        mergeSort(m, e, n);
        merge(s, e, m, n);
    }
}

您的代码中还有其他问题，特别是：

你应该在dereferencinga1[i]anda2[j]之前检查偏移量i和j `.

偏移k不应该在合并阶段直接使用，你应该存储到n[s + k].

在 a2 的初始化循环中，您应该使用 a2[j] = n[m + j]; 而不是 a2[j] = n[s + m + j];

另请注意，在 C 中传递包含第一个索引并排除最后一个索引的范围是惯用的。这允许传递空范围，而您当前的方法不允许。它还使代码更简单易读。

这是修改后的版本：

#include <stdio.h> void merge(int s, int e, int m, int n[]) { int l1 = m - s; int l2 = e - m; int a1[l1]; int a2[l2]; for (int i = 0; i < l1; i++) { a1[i] = n[s + i]; } for (int j = 0; j < l2; j++) { a2[j] = n[m + j]; } for (int i = 0, j = 0, k = 0; k < l1 + l2; k++) { if (i < l1 && (j >= l2 || a1[i] <= a2[j])) { n[s + k] = a1[i]; i++; } else { n[s + k] = a2[j]; j++; } } } void mergeSort(int s, int e, int n[]) { if (e > s + 1) { int m = s + (e - s) / 2; mergeSort(s, m, n); mergeSort(m, e, n); merge(s, e, m, n); } } int main(void) { int n[] = { 4, 3, 2, 1 }; int r = sizeof(n) / sizeof(n[0]); mergeSort(0, r, n); for(int i = 0; i < r; i++) { printf("%i\n", n[i]); } return 0; }

Merge Sort Error : Segmentation Fault

Merge Sort Error : Segmentation Fault

c

sorting

algorithm

mergesort

array-algorithms