分段错误:11 合并排序

Question

>我尝试实现合并排序算法，但出现分割错误。为什么？错误似乎出在合并排序函数中。合并排序函数（在第二次调用时）何时应仅检查 4 个数字的数组（长度应为 4）显示长度 = 27。为什么？（在包含 8 个元素的数组上测试）

#include<iostream>
using namespace std;
int n, A[1000];
void citire(int lungime) {
    for (int i = 0; i < lungime; i++) cin >> A[i];
}
void afisare(int lungime) {
    for (int i = 0; i < lungime; i++)
        cout << A[i] << " ";
    cout << 'n';
}
int lungime(int A[]) {
    int i = 0;
    while (A[i]) i++;
    return i;
}
void Merge(int L[], int R[], int A[]) {
    int nL = lungime(L);
    int nR = lungime(R);
    int i = 0, j = 0, k = 0;
    while (i < nL && j < nR) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < nL) {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < nR) {
        A[k] = R[j];
        j++;
        k++;
    }
}

void MergeSort(int A[]) {
    int n1 = lungime(A);
    if (n1 < 2) return;
    else
    {
        int mid = (int)n1 / 2;
        int L[mid];
        int R[n - mid];
        for (int i = 0; i < mid; i++)
            L[i] = A[i];
        for (int i = mid; i < n; i++)
            R[i - mid] = A[i];
        MergeSort(L);
        MergeSort(R);
        Merge(L, R, A);
    }
}

int main() {
    cin >> n;
    citire(n);
    MergeSort(A);
    afisare(n);
    return 0;
}

Answer 1

本例中所做的更改。A[]、L[]、R[] 使用 new 进行分配。A[] 作为参数传递。L[] 和 R[] 在 Merge（） 中分配。大小和/或索引作为参数传递，lungime（） 不再用于获取大小。评论中提到的其他变化。

#include<iostream>
using namespace std;
void citire(int A[], int lungime) {     // A is parameter
    for (int i = 0; i < lungime; i++) cin >> A[i];
}
void afisare(int A[], int lungime) {    // A is parameter
    for (int i = 0; i < lungime; i++)
        cout << A[i] << " ";
    cout << 'n';
}
// A, low, mid, end are parameters
// L and R allocated here
void Merge(int A[], int low, int mid, int end) {
    int sizeL = mid-low;
    int sizeR = end-mid;
    int *L = new int[sizeL];
    int *R = new int[sizeR];
    for(int i = 0; i < sizeL; i++)
        L[i] = A[low+i];                // A[low+i]
    for(int i = 0; i < sizeR; i++)
        R[i] = A[mid+i];                // A[mid+i]
    int i = 0, j = 0, k = low;          // k = low
    while (i < sizeL && j < sizeR) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < sizeL) {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < sizeR) {
        A[k] = R[j];
        j++;
        k++;
    }
    delete[] R;
    delete[] L;
}
// A, low, end are parameters
void MergeSort(int A[], int low, int end) {
    int sizeA = end - low;
    if(sizeA < 2)
        return;
    int mid = low + (sizeA / 2);        // mid = low + ...
    MergeSort(A, low, mid);
    MergeSort(A, mid, end);
    Merge(A, low, mid, end);
}
int main() {
    int n;
    cin >> n;
    int *A = new int[n];                // A is allocated
    citire(A, n);                       // A, n are parameters
    MergeSort(A, 0, n);                 // A, 0, n are parameters
    afisare(A, n);                      // A, n are parameters
    delete[] A;
    return 0;
}

Answer 2

"lungime函数是字符串的长度，这个函数效果很好。我已经在不同的阵列上测试过它"。好吧，这纯粹是偶然的;未初始化的内存可以包含零，并意外提供数组终止符。如果要保留当前设计，则应：

• 将 A 初始化为零
• 确保输入流中的元素不超过 999 个，
• 没有元素的值为零，因为零被保留并用作终止符，并且
• 定义 L 和 R（在 MergeSort 中）一个元素，并将最后一个元素初始化为零。

除非有压倒性的理由支持"自己推出"排序解决方案，否则您可以查看预制件排序支持。C++中的向量类正好提供了这一点。