c++ 为什么在这种合并排序中会出现分段错误？

9lowa7mx 于 2022-11-27 发布在其他

关注(0)|答案(1)|浏览(143)

我在不同的编译器上编译了这段代码，但是所有的编译器都给出了运行时错误。有人能告诉我这段代码有什么问题吗？

void merge(int *str, int beg, int mid, int end) {
    int *arr = new int[end - beg + 1];
    int k = 0;
    int i = beg;
    int j = mid + 1;
    while (i <= mid && j <= end) {
        if (str[i] < str[j]) {
            arr[k] = str[i];
            i++;
            k++;
        } else {
            arr[k] = str[j];
            j++;
            k++;
        }
    }
    while (i <= mid) {
        arr[k] = str[i];
        i++;
        k++;
    }
    while (j <= end) {
        arr[k] = str[j];
        //here i got buffer overrun while writing to arr
        j++;
        k++;
    }
    for (i = beg; i <= end; i++) {
        str[i] = arr[i - beg];
    }
    delete[] arr;
}

void merge_sort(int *str, int beg, int end) {
    
    if (beg >= end)
        return;

    int mid = (end - beg) / 2;
    merge_sort(str, beg, mid);
    merge_sort(str, mid + 1, end);
    merge(str, beg, mid, end);
}

这个代码几乎是一样的，我发现在Sanfoundry，但那一个是工作，但我得到了一些错误。

c++

来源：https://stackoverflow.com/questions/72582599/why-is-there-segmentation-fault-in-this-merge-sort

1条答案

按热度按时间

6qfn3psc1#

merge_sort中的中点计算不正确：您应该写入以下内容而不是int mid = (end - beg) / 2;：

int mid = beg + (end - beg) / 2;

另请注意，您的API可能会混淆，因为mid似乎是左半部分最后一个元素的索引的结尾，而end是右半部分最后一个元素的索引。将mid指定为右半部分第一个元素的索引，将end指定为右半部分之后的第一个元素的索引要简单得多，也不容易出错。按照此约定，初始调用为：

merge_sort(array, 0, array_length);

下面是一个修改后的版本，使用类型size_t作为索引和长度变量：

void merge(int *str, size_t beg, size_t mid, size_t end) {
    int *arr = new int[end - beg];
    size_t i = beg;
    size_t j = mid;
    size_t k = 0;

    while (i < mid && j < end) {
        if (str[i] <= str[j]) {
            arr[k++] = str[i++];
        } else {
            arr[k++] = str[j++];
        }
    }
    while (i < mid) {
        arr[k++] = str[i++];
    }
    while (j < end) {
        arr[k++] = str[j++];
    }
    for (i = beg; i < end; i++) {
        str[i] = arr[i - beg];
    }
    delete[] arr;
}

void merge_sort(int *str, size_t beg, size_t end) {
    if (end - beg >= 2) {
        size_t mid = beg + (end - beg) / 2;
        merge_sort(str, beg, mid);
        merge_sort(str, mid, end);
        merge(str, beg, mid, end);
    }
}

赞(0）回复(0）举报 2022-11-27

我来回答

c++ 为什么在这种合并排序中会出现分段错误？

1条答案

相关问题

热门标签

最新问答