1

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

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。因此合并排序出错了。请帮我解决我哪里出错了。

4

1 回答 1

1

有很多事情是错误的，首先是没有进行实际的合并。a[100]你在你的函数中“合并”到一个本地数组中merge()，然后用来之不易的努力完全没有做任何事情。调用方保持不变，正如他们所说，就是这样。

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

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

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

简而言之，您可以 (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);
}
于 2013-10-26T03:41:33.150 回答