自底向上归并排序

Question

我有以下用于自下而上合并排序的代码，它对文件进行操作，每一次合并都会将 m 加倍，这是代码，

#include <iostream>
#include <vector>
using namespace std;

inline int Min(int a,int b)
{
    return a<b?a:b;
}

void merge(int a[],int l,int m,int r)
{
    vector<int>b;
    int i, j;
    for (i=m+1;i>=l;i--)  b[i-1]=a[i-1];
    for (j=m;j<r;j++) b[r+m-j]=a[j+1];
    for (int k=l;k<=r;k++)
        if ( b[j]<b[i]) 
            a[k]=b[j--];  
        else
            a[k]=b[i++];
}

void mergesort(int a[],int l,int r)
{
    for (int m=1;m<=r-l;m=m+m)
        for (int i=l;i<=r-m;i+=m+m)
            merge(a,i,i+m-1,Min(i+m+m-1,r));
}

int main()
{
    int a[]={12,4,7,3,9,8,10,11,6};
    int n=sizeof(a)/sizeof(int);
    mergesort(a,0,n-1);
    for (int i=0;i<n;i++)
    {
        cout<<a[i]<< "  ";
    }

    return 0;
}

但是当我运行此代码时，出现异常，表明发生了向量超出范围错误，请帮助

Answer 1

您尚未初始化矢量以使其包含任何数据。

我想这是一个练习，这就是为什么你要重新发明轮子。我不确定这是使用单字符标识符的借口，这会使您的代码难以理解。

如果 a 是一个数组，l 是它的长度，您可以初始化 b ，

vector<int> b( a, a+l );

大概您正在创建数组的临时克隆以进行排序。

顺便问一下，合并排序不是递归的吗？我没看到你的情况。

我的代码也有其他问题，例如，您的缩进表明 for 循环是嵌套的，但与 for 语句位于同一行的语句后面的分号表明不然。我建议你总是在循环上使用大括号。

Answer 2

在函数 merge 中，您有 vectorb; b 的大小为 0。您应该rezise()您的向量，或使用数组初始化它：

vector<int> v(arr, arr+size);

Answer 3

您将 b 创建为空向量，然后开始寻址其元素。它的大小为 0，因此无效。你应该给它一个更大的尺寸。

Answer 4

其他人已经解决了尝试在空向量中索引元素的问题。此外，以下循环存在问题：

for (i=m+1;i>=l;i--)  b[i-1]=a[i-1];

循环的最后一次迭代有 i=l 并且您寻址向量/数组的 [i-1] 元素。当l=0时，这是索引-1并且对于向量和数组来说都超出范围。