0

从伪代码实现算法时出现两个错误：

我的问题之一是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 . . .

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

4

2 回答 2

3

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

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 */
    }

其他的建议：

全部为 MERGE MERGESORT 的标识符通常是为宏保留的。如果您使用它们，您可能会遇到问题。首选混合大小写的函数名称。

您可以使用向量模拟数组：

// 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) 的迭代器编写的。我认为如果你适应这种风格，你会发现你的算法更容易实现。

于 2013-10-25T23:44:13.393 回答
2

您的代码有几个问题，我在评论中指出了它们。这是最接近您的代码的解决方案，但远非最佳。考虑使用 C++ 容器，std::vector例如。命名至少是有争议的，当然归并排序应该作为一种就地算法来实现。

//L and R are auxiliary arrays 
//preallocated with (inputSize/2 + 1) constant size
void MERGE(int *A, int p, int q, int r, int* L, int* R)
{
    if (p > q || q > r)
    {
        return;
    }

    int n1 = q - p + 1;
    int n2 = r - q;

    // note 0-based indices
    int i = 0;
    int j = 0;

    for(;i < n1;i++)
    {
        L[i] = A[p + i];
    }

    for(;j < n2;j++)
    {
        R[j] = A[q + j + 1];  //+1 because p + n1 - 1 == q + 0
    }

    //again - note 0-based indices
    i = 0;
    j = 0;

    for (int k = p; k <= r; ++k)
    {
        // The most important fix - in your code you didn't check
        // for left/right array bounds at all.
        // Sentinel values aren't needed - size is known
        if(i < n1 && (j >= n2 || L[i] <= R[j]))
        {
            A[k] = L[i];
            ++i;
        }
        else if (j < n2)
        {
            A[k] = R[j];
            ++j;
        }
    }
}

void MERGESORT(int* A, int p, int r, int* L, int* R)
{
    if (p < r)
    {
        int q = (p + r) / 2;  //floor was redundant
        MERGESORT(A, p, q, L, R);
        MERGESORT(A, q+1, r, L, R);

        MERGE(A, p, q, r, L, R);
    }
}

void MERGESORT(int* A, int size)
{
    int*L = new int[size/2 + 1]; //preallocate auxiliary arrays
    int*R = new int[size/2 + 1]; //size/2 + 1 is what will be needed at most

    MERGESORT(A, 0, size - 1, L, R);

    delete L;
    delete R;
}

int main()
{
    int A[5]{ 7474, 28268, 32506, 13774, 14411 };

    MERGESORT(A, 5);

    for (int i = 0;i < 5;++i)
    {
        std::cout << A[i] << std::endl;
    }

    return 0;
}

输出：

7474
13774
14411
28268
32506

归功于 DyP发现了之前版本中的所有错误：）

于 2013-10-25T23:56:37.027 回答