尝试删除分配的数组l_sorted和r_sorted在c++中时出错

Question

这是我的代码来实现合并算法。

它很有效而且很有效率。但是，当我尝试删除分配的数组l_sorted和r_sorted时，会发生错误。错误是: malloc：*对象0x7fa7b3501330:指针被释放的错误没有分配给我很多，但没有找到任何解决方案。

我怎么才能解决这个问题？

#include <iostream>
#include <stdlib.h>
using namespace std;

void merge(int L[],int R[],int size,int *a_sorted, bool even)
{
    if (even == 1)
    {
        int l=0,r=0;
        for (int i=0;i<size*2;i++)
        {
            if ((L[l]<=R[r] && l<size) || (r>=size && l<size))
            {
                a_sorted[i]=L[l];
                l++;
            }
            else
            {
                a_sorted[i]=R[r];
                r++;
            }
        }
    }

    else
    {
        int l=0,r=0;
        for (int i=0;i<size*2+1;i++)
        {
            if ((L[l]<=R[r] && l<size) || (r>=size+1 && l<size))
            {
                a_sorted[i]=L[l];
                l++;
            }
            else
            {
                a_sorted[i]=R[r];
                r++;
            }
        }
    }
}

int* merge_sort(int a[],int size,int *a_sorted)
{
    if (size == 1)
        return a;

    if(size%2==0)
    {
        int mid=size/2;
        int *L=(a);
        int *R=(a+mid);
        int *l_sorted=new int[mid];
        int *r_sorted=new int[mid];
        l_sorted = merge_sort(L,mid,l_sorted);
        r_sorted = merge_sort(R,mid,r_sorted);
        merge(l_sorted,r_sorted,mid,a_sorted,1);
        delete []l_sorted;
        delete []r_sorted;
    }

    else{
        int mid=size/2;
        int *L=a;
        int *R=a+mid;
        int *l_sorted=new int[mid];
        int *r_sorted=new int[mid+1];
        l_sorted = merge_sort(L,mid,l_sorted);
        r_sorted = merge_sort(R,mid+1,r_sorted);
        merge(l_sorted,r_sorted,mid,a_sorted,0);
        delete []l_sorted;
        delete []r_sorted;
    }


    return a_sorted;
}



int main()
{
    const int s=2;
    clock_t start1=clock();
    int *a=new int[s];
    srand(time(0));
    for (int i=0;i<s;i++){
        a[i]=rand()%(s*2);
    }
    int *b=new int[s];
    clock_t end1=clock();
    clock_t start2=clock();
    b=merge_sort(a,s,b);
    clock_t end2=clock();
    for (int i=0;i<s;i++){
        cout<<b[i]<<endl;
    }
    cout<<"Time taken for mergesort: "<< (double)(end2-start2)/(CLOCKS_PER_SEC)<<endl;
    cout<<"Time taken for generate: "<< (double)(end1-start1)/(CLOCKS_PER_SEC)<<endl;   
}

Answer 1

首先，代码有什么问题。稍后我会进一步简化算法，但现在.在你的分而治之的两大块中，你要做以下几件事：

首先，将入站数组划分为左、右两个子部分(以“偶数”块为例)。

int mid=size/2;
int *L=(a);
int *R=(a+mid);

然后将两个大小相似的数组分配给分区。

int *l_sorted=new int[mid];
int *r_sorted=new int[mid];

最后，调用递归。现在仔细看看作为第一个参数传递的是什么：

l_sorted = merge_sort(L,mid,l_sorted);
r_sorted = merge_sort(R,mid,r_sorted);

但是L和R不能保证是在这个函数中进行的分配。实际上，R不一定会在这个函数中被分配给。R总是L数组中的一些偏移量。现在看看在递归的基中返回了什么(递归停止并弹出的情况)：

if (size == 1)
    return a;

这意味着如果长度为1，则返回L或R，但R不是分配；它是对另一个数组(可能是分配)的偏移。所以当你这么做的时候

r_sorted = merge_sort(R,mid,r_sorted);

您刚刚更改了r_sorted指向的内容。它不再指向你所做的分配。现在它指向l_sorted数组中的一些偏移量，从调用堆栈中的一步高出一步。因此，boom.同样的事情发生在l_sorted赋值上，但是在这种情况下，当您分配入站向量时，您实际上做了两件事：

1. 在相同的激活范围(相同的函数调用)中泄漏原始分配
2. 删除调用方传入的数组(传入的数组为a[] )

我不应该，瓦兰会抓住一吨这样的东西。

如果你想做的是一个自上而下的合并排序，有相当容易的方法。但传统的自下而上更容易理解，下面将展示这一点。

传统的自下而上合并排序

在对递归算法进行编码时，向问题抛出更多代码只会导致更大的问题出现，而这一点也不例外。你把事情搞得太复杂了。从合并函数开始。

合并应该采用三个参数。段基、中点偏移量和总长度：

void merge(int ar[], int mid, int len)

有两段正在排序：

a[0] ... a[mid-1]
a[mid] ... a[len-1]

在非内部合并中完成此操作所需的临时空间为len (相信我，此时您不想试图对就地算法进行编码)。完全没有必要使用偶数边界专门化代码。尽管很难相信，以下是传统合并排序中最困难的部分，而且这里没有太多内容：

merge() ：长版本

void merge(int a[], int mid, int len)
{
    int *tmp = new int[len];
    int i=0, j=mid, k=0;

    while (i<mid && j<len)
    {
        // x will reference the index (i or j) we're bumping
        int& x = (a[i] < a[j]) ? i : j;
        tmp[k++] = a[x++];
    }

    // one of the two segments didn't finish. we don't really care which
    //  one, as we'll be ensuring *both* did.
    while (i < mid)
        tmp[k++] = a[i++];
    while (j < len)
        tmp[k++] = a[j++];

    // tmp[] is now fully sorted. just dump the content back
    //  into a[]; *all of it*.
    for (i=0; i<len; ++i)
        a[i] = tmp[i];

    // delete temp space
    delete [] tmp;
}

merge() ：较短版本的

void merge(int a[], int mid, int len)
{
    std::vector<int> tmp;
    tmp.reserve(len);
    std::merge(a, a+mid, a+mid, a+len, std::back_inserter(tmp));
    std::copy(tmp.begin(), tmp.end(), a);
}

merge() ：最短版本

根本不要写一个合并，只需使用：

std::inplace_merge(a, a+len/2, a+len);

无论使用哪种方法，结果的合并排序算法都会变成下面的结果，所有偶数和奇数分区逻辑都会被压缩。注意:这使用简单指针算法来指定rhs段的起始位置，该位置始终是a+len/2。

void mergesort(int a[], int len)
{
    if (len < 2)
        return;

    mergesort(a, len/2);
    mergesort(a+len/2, len-len/2);
    merge(a, len/2, len); // or use std::inplace_merge(a, a+len/2, a+len);
}

现在，您只需要正确地从main()调用这个

int main()
{
    clock_t start1=clock();

    static const int N = 30;
    int a[N];

    srand((unsigned int)time(NULL));

    for (int i=0; i<N; ++i)
    {
        a[i] = rand() % (2*N);
        std::cout << a[i] << ' ';
    }
    std::cout << '\n';
    clock_t end1=clock();

    mergesort(a,N);
    clock_t end2=clock();

    for (int i=0; i<N; ++i)
        std::cout << a[i] << ' ';
    std::cout << '\n';

    std::cout<<"Time taken for generate: "<< (double)(end1-start1)/(CLOCKS_PER_SEC)<<std::endl;
    std::cout<<"Time taken for mergesort: "<< (double)(end2-end1)/(CLOCKS_PER_SEC)<<std::endl;

    return 0;
}

示例输出(明显不同)

18 26 38 55 12 38 31 35 46 32 14 26 42 3 10 13 37 21 24 21 11 15 55 10 55 19 47 19 28 53 
3 10 10 11 12 13 14 15 18 19 19 21 21 24 26 26 28 31 32 35 37 38 38 42 46 47 53 55 55 55 
Time taken for generate: 6.1e-05
Time taken for mergesort: 1e-05

我只能希望这能帮上忙。有明显的方法可以提高效率，有些方法比其他方法更明显。例如，您知道您将永远不需要比len更多的额外空间，因此您可以在算法深入之前分配整个临时空间，并在每次调用之后将其参数化。这将消除除一个外的所有内存分配。您还可以通过使用更智能的分配(例如使用merge()的更短的std::vector<>算法来演示)来实现这种基于RAII的方法。只是思考的食粮。