c++ - 我的合并排序算法没有得到正确答案

Question

我是 C++ 和算法的新手。我对自己编写的合并排序算法感到困惑。我不知道为什么代码在没有错误的情况下没有得到正确的答案。在代码中，我想对输入的 5 个数字进行排序。但排序后的数组不会打印在屏幕上。我想知道我的代码中的问题。非常感谢。

#include<iostream>
using namespace std;
int merge(int a[], int low, int mid, int high) {
    int h = low; int j = mid + 1; int k = low;
    int *b = new int[high - low + 1];
    while ((h <= mid) && (j <= high)) {
        if (a[h] < a[j])
            b[k++] = a[h++];
        else
            b[k++] = a[j++];

    }
    if (h > mid) {
        for (j; j <= high;++j)
            b[k++]=a[j];
    }
    if (j > high) {
        for (h; h <= mid; ++h)
            b[k++] = a[h];
    }
    for (int i = low; i <= high; ++i)
        a[i] = b[i];
    delete []b;
    return 0;
}
int MergeSort(int a[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    return 0;
}

int main() {
    int const n(5);
    int a[n];
    cout << "Input " << n << " numbers please:";
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    MergeSort(a, 0, n - 1);
    for (int i = 0; i <= n - 1; ++i)
        cout << a[i] << " ";
    cout << endl;
}

Answer 1

MergeSort函数 - 假设 low + 1 == high因此mid==low .

递归调用MergeSort(a, low, mid)将立即返回，而 MergeSort(a, mid, high)将再次通过相同的low和 high - 直到您的应用程序溢出堆栈(并且您将再次发布关于 SO 的问题？)

---

merge函数，假设 low==3 , mid==4 , high==5 .

你分配一个b[]的 3 .到目前为止一切顺利。

但是你从 k=low 开始(即 3)并执行 b[k++] 的分配- 当你在 b[4] 写作时，在接下来的步骤中已经越界了和 b[5] (而 b[0] 和 b[1] 将保持不变)。

等等(包括for (int i = low; i <= high; ++i) a[i]=b[i];)

您可能想要做的是使用 - low 执行对临时存储的所有分配。偏移量(b[k-low] 后跟 k++ 在 while 循环结束时)。