c++ - 在 Mergesort 中执行了错误的子数组

Question

我已经使用递归实现了归并排序。涉及的两个函数的代码如下:

void merge(int la[50],int ra[50],int lsize,int rsize)
{
    cout<<"\nLEFT Array\n";
    for(int i=0;i<lsize;i++)
    {
        cout<<la[i]<<" ";
    }
    cout<<"\nRIGHT Array\n";
    for(int i=0;i<rsize;i++)
    {
        cout<<ra[i]<<" ";
    }
    int a[100],i,j,k;
    i=0;
    j=0;
    k=0;
    while((i<lsize)&&(j<rsize))
    {
        if(la[i]<ra[j])
        {
            a[k]=la[i];
            k++;
            i++;
        }
        else
        {
            a[k]=ra[j];
            k++;
            j++;
        }
    }
    while(i < lsize)
    {
        a[k]=la[i];
        k++;
        i++;
    }
    while(j < rsize)
    {
        a[k]=ra[j];
        k++;
        j++;
    }
    cout<<"\nMERGED\n";
    for(int i=0;i<k;i++)
    {
        cout<<a[i]<<" ";
    }
}

void mergesort(int a[100],int n)
{
    if(n == 1)
    {
        return;
    }
    else
    {
        int ra[50],la[50],lsize,rsize;
        lsize = n/2;
        rsize = n-lsize;
        cout<<"\nLA\n";
        for(int i=0;i<lsize;i++)
        {
            la[i]=a[i];
            cout<<la[i]<<" ";
        }
        cout<<"\nRA\n";
        for(int i=0;i<rsize;i++)
        {
            ra[i]=a[lsize+i];
            cout<<ra[i]<<" ";
        }
        mergesort(la,lsize);
        mergesort(ra,rsize);
        merge(la,ra,lsize,rsize);
    }
}

然而，在递归过程中，如果合并后的子数组是例如 1,2,5，那么下次在合并函数中使用它时，数组将被用作 2,1,5 或其他随机的。因此，我没有得到正确的排序输出。例如，我输入的未排序数组为 3,5,1,4,2。这里发生的是合并排序正确进行，直到合并函数期间形成的合并数组 2,4 之一在用于计算更大的子数组时变为 4,2 的阶段。因此合并排序出错。请帮我解决我哪里出错了。

Answer 1

有很多错误，从没有实际合并开始。您在 merge() 函数中“合并”到一个本地数组 a[100] 中，然后继续做任何来之不易的努力。调用方保持不变，正如他们所说，就是这样。

其次，这里的固定尺寸不应该出现。根据其定义，该算法旨在处理任意长度，并且应该这样实现。

关于合并排序算法的几件事是基础的。除非您拥有特别令人印象深刻的就地合并算法(它们确实存在，但它们并非微不足道)，否则您将执行以下两种操作之一来拆分或合并数据:

• 将当前列表拆分为两个子列表，将每个子列表复制到临时存储，然后递归，然后在递归展开时将这两个临时片段合并回原始列表。
• 仅按标记拆分当前列表，通过递归传递每个列表+长度，并合并到临时存储中，然后复制到原始容器中。

简而言之，您可以 (a) 拆分到临时存储、递归、合并到原始，或 (b) 仅索引拆分、递归、合并到临时、复制到原始。这是你的选择。下面是一个执行后者的算法，如果您对它的简单性并不感到惊讶，您应该感到惊讶(但还有一个更好的方法，我将在最后展示):

#include <algorithm>
#include <vector>

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);

    std::vector<int> temp(N);
    std::merge(arr, arr+mid, arr+mid, arr+N, temp.begin());
    std::copy(temp.begin(), temp.end(), arr);
}

---

使用上述算法的示例程序如下:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <random>

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);

    std::vector<int> temp(N);
    std::merge(arr, arr+mid, arr+mid, arr+N, temp.begin());
    std::copy(temp.begin(), temp.end(), arr);
}

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<int> dist(1,100);

    int arr[25];
    std::generate_n(arr, 25, [&](){ return dist(rng); });

    // copy to stdout
    std::copy(std::begin(arr), std::end(arr),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    // mergesort
    mergesort(arr, 25);

    // copy to stdout
    std::copy(std::begin(arr), std::end(arr),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

输出(你的显然会有所不同)

98 91 87 25 60 41 16 18 10 72 68 35 16 80 46 17 56 44 78 92 57 63 66 82 63 
10 16 16 17 18 25 35 41 44 46 56 57 60 63 63 66 68 72 78 80 82 87 91 92 98 

---

使用就地合并的 C++ 方法

还记得关于拥有就地合并算法有多特别好的评论吗？你猜怎么着？ C++ 标准库提供了一个:std::inplace_merge .这使得我们的合并排序算法在其简单性方面可以与插入排序相媲美:

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);
    std::inplace_merge(arr, arr+mid, arr+N);
}