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

Question

我是 C++ 新手，algorithm.I 对我编写的合并排序算法感到困惑。我不知道为什么代码在没有错误的情况下没有得到正确的答案。在代码中，我想对输入的 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) 的递归调用将立即 return，而 MergeSort(a, mid, high) 将再次传递相同的 low 和 high - 直到您的应用程序溢出堆栈（您将 post 再次提出有关 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循环）。

Answer 2

我只发现了一个小问题。试试这个简单的修复。

for (int i = 0; i <= n - 1; ++i) {
        cout << a[i] << " ";
        cout << endl;
   }

您的代码在 for 语句中缺少括号。此代码在我的计算机上通过此修复工作。

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

My Merge Sort algorithm don't get a correct answer

c++

sorting

algorithm

mergesort