c - 合并排序错误: Segmentation Fault

Question

我收到错误段错误:11，请帮忙。变量 info:(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

m的计算因为中间元素是假的:你得到 m 的偏移量来自s ，而不是它在数组中的索引。

这是更正后的版本:

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);
    }
}

您的代码中还存在其他问题，特别是:

• 您应该检查偏移量 i和j 之前 dereferencing a1[i] and a2[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;
}