合并排序与递归

Question

    /*
This code is Written by Shankhadeep Dey
(15th Aug 2018)
*/
#include<iostream>
using namespace std;
void merge(int a[],int p,int q,int r)
{
    int n1,n2,j,i,k;
    n1= q-p+1;
    n2= r-q;
    int L[n1],R[n2];
    for (i = 0; i < n1-1; ++i)
        L[i]=a[p+i-1];
    for (j = 0; j < n2-1; ++j)
        R[j]=a[q+j];
    L[n1]=1e9;
    R[n2]=1e9;
    i=0;
    j=0;
    for (k = p; k < r; ++k)
    {
        if (L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }
    while (i < n1)
    {
        a[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        a[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int a[],int p,int r)
{
    int q;
    if (p<r)
    {
        q= (p+r)/2;
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);
        merge(a,p,q,r);
    }
}
int main()
{   int w[4]={4,3,21,5};
    mergeSort(w,0,3);
    for (int i = 0; i < 4; ++i)
    {
        cout<<w[i]<<" ";
    }
    cout<<endl;
}

谁能告诉我为什么这个排序不起作用？ 我从 "Introduction to Algorithm" 书中尝试了这个算法，但我不太确定为什么这个代码不是运行。我尝试在线搜索合并排序并找到了很多东西，但我确实想知道我的代码有什么问题。输出是：-0 1000000000 1 1000000000（这不是正确的答案）。
这是我收到的警告

mergeSort.cpp: In function ‘void merge(int*, int, int, int)’:
mergeSort.cpp:12:10: warning: ISO C++ forbids variable length array ‘L’ [-Wvla]
  int L[n1],R[n2];
          ^
mergeSort.cpp:12:16: warning: ISO C++ forbids variable length array ‘R’ [-Wvla]
  int L[n1],R[n2];

Answer 1

您的合并逻辑存在问题。想一想当您想要合并数组中的前两个元素时会发生什么。在这种情况下，p=0、q=0 和 r=1。在这种情况下 n1=0，下面的循环永远不会执行：

for (i = 0; i < n1-1; ++i)
    L[i]=a[p+i-1];

与下一个循环相同。更糟糕的是，如果您通过将 n1-1 更改为 n1 来修复它，那么在第一次迭代中，p+i-1 将是 -1，这会导致更多问题。

如果你想通过比较一个可行的解决方案来作弊，我相信 How to implement merge sort from "The Introduction to Algorithms" by Cormen and Co

上有一个

更一般地说，我建议使用逐行调试器（gdb 或使用像 Eclipse 这样的 IDE），这样您就可以逐行调试代码，检查什么时候执行什么，什么时候执行每一步的变量值是什么。这使得诊断此类错误变得更加容易。

（注意：此问题已在问题编辑中修复）。

这些行有问题：

for (int i = 0; i < n2-1; ++i)
    R[j]=a[q+j];

使用 j 或 i，但不能同时使用。目前您正在使用 j 的未初始化值。

附带说明一下，您声明了变量 i 和 j 两次（一次在函数顶部附近，另一次在 for 循环中）。这不会阻止程序运行，但在不同范围内使用两个同名变量并不是很好的做法，因为它可能会引起混淆。

此外，在这一行中：

q= (int)(p+r)/2;

(int) 部分什么都不做，可能会误导 reader。 p 和 r 已经是整数，因此编译器使用整数除法产生整数结果。

合并排序与递归

merge sort with recurrsion

c++

sorting

recursion

merge

mergesort