c++ - C++ 中的合并排序实现问题

Question

我在从伪代码实现算法时遇到两个错误:

我的一个问题是 int L[n1+1]; 错误:需要是一个常量；无法分配常量大小 0。运行它的唯一方法是将大小设为 10 之类的数字。我可能错误地实现了伪代码，这就是为什么我在上面包含了语句。这可能是我下一个问题的原因。

我的另一个问题是我只打印了一行未排序的代码。我的打印功能完美无缺，适用于所有分类程序。我相信 MERGE 功能只运行一次。我在底部发布了排序的输出。

我有一个数组 A 的随机数生成器，从 0 到 RAND_MAX。初始调用是 MERGESORT(A,1,n);

void MERGE(int *A, int p, int q, int r)
{
    int n1 = q-(p+1);
    int n2 = r-q;

  //psuedocode states, let L[1..n1+1] & R[1..n1+1] be new arrays

    int L[n1+1];        
    int R[n2+1];    

    for(int i=1; i<n1;i++)
    {
        L[i]=A[p+(i-1)];
    }
    for(int j=1; j<n2; j++)
    {
        R[j] = A[q+j];
    }
    L[n1+1]=NULL; //sentinel
    R[n2+1]=NULL; //sentinel
    int i=1;
    int j=1;
    for (int k=p; k<r; k++)
    {
        if(L[i]<=R[j])
        {
            A[k]=L[i];
            i=i+1;
        }
        else
        {
            A[k]=R[j];
            j=j+1;
        }
    }
}

void MERGESORT(int *A,int p, int r)
{
    if (p<r)
    {
        int q=floor((p+r)/2);
        MERGESORT(A,p,q);
        MERGESORT(A,q+1,r);
        MERGE(A,p,q,r);
    }
}

使用 int L[10]; 和我的 A[10]; 我的输出是:

Sort:  7474 28268 32506 13774 14411
Press any key to continue . . .

如果有人可以帮助解决这两个问题，我很可能会让它工作。

Answer 1

您未能检测到合并数组的结尾:

for (int k=p; k<r; k++)
{

    // You need to check that i/j are still in range.
    // otherwise the following test are not valid.

    if ((i < n1) && (j < n2))
    {
      if(L[i]<=R[j])
      {
        A[k]=L[i];
        i=i+1;
      }
      else 
      {
        A[k]=R[j];
        j=j+1;
      }
    }
    else
    {   /* More work here */
    }

其他评论:

凡是capitol MERGE MERGESORT的标识符一般都是为宏保留的。如果你使用它们，你很可能会遇到问题。首选大小写混合的函数名称。

你可以用 vector 模拟数组:

// Simulate L[1..n1+1]
minI = 1;
maxI = n1-1;
std::vector<int> const L(A+(minI-1), A+(maxI-1));     

C++ 中的数组是零索引的。您似乎遇到了一个错误(尤其是在访问数组末尾时)。我建议您从 0 而不是 1 开始计数。大多数 C++ 代码是根据 [begining..1PastEnd) 中的迭代器编写的。如果您采用这种风格，我认为您会发现您的算法更容易实现。