时间戳

首页 > 解决方案 > 分段错误、合并排序算法

c++ - 分段错误、合并排序算法

问题描述

这是我写的一个归并排序算法。虽然它适用于较小的数组，但它会为包含超过 7/8 个元素的数组提供分段错误。在某些重复数字的情况下，它也会失败。例如 - {5,5,1,2,1}。我一直在尝试找出错误但无济于事

我知道代码并不完全有效，但我现在正专注于让它工作。有关代码改进的建议将很有帮助。先感谢您。

#include <iostream>
using namespace std;
void printarray(int a[], int size);
void splitsort(int b[], int start, int end); //Split array into half
void merge(int b[], int start, int end); // merge the sorted arrays

int main()
{
    cout << "This is merge sort" << endl;
    int array[] = { 9,8,7,6,5,4,3,2,1 };
    int length = sizeof(array) / sizeof(array[0]);
    printarray(array, length);
    splitsort(array, 0, length - 1);
    cout << "sorted array" << endl;
    printarray(array, length);
    return 0;
}

void printarray(int a[], int size) {
    for(int i = 0; i<size; i++) {
        cout << a[i] << ",";
    }
    cout << endl;
    return;
}

void splitsort(int b[], int start, int end) {
    //base case
    if(end == start) { return; }

    //
    splitsort(b, start, (start + end) / 2);
    splitsort(b, (start + end) / 2 + 1, end);
    merge(b, start, end);

    return;
}

void merge(int b[], int start, int end) {
    int tempb[(end - start) + 1];

    //base case
    if(end == start) { return; } // if single element being merged
    int i = start;
    int j = (start + end) / 2 + 1;
    for(int k = start; k <= end; k++) {
        if(i == (start + end) / 2 + 1) { tempb[k] = b[j]; j++; }// finished first array
        else if(j == end + 1) { tempb[k] = b[i]; i++; }// finished second array
        else if(b[i] >= b[j]) {
            tempb[k] = b[j];
            j++;
        }
        else if(b[j] >= b[i]) {
            tempb[k] = b[i];
            i++;
        }
    }

    for(int k = start; k <= end; k++) {
        b[k] = tempb[k];
    }

    return;
}

标签： c++mergesort

解决方案

int tempb[(end - start) + 1];

tempb最多可以有 2 个元素，而 mainarray有 10 个元素。您最终访问tempb[9]，导致分段错误。

要解决此问题，请将大小更改为int tempb[max_size];之前计算max_size的大小arrayint length = sizeof(array) / sizeof(array[0]);

更改tempb为std::vector<int> tempb(max_size)将有助于调试以及符合 C++ 标准。

推荐阅读