0

我正在为 C++ 中的自下而上合并排序编写代码，但此错误发生在我将内存分配给指针的行上，

void merge(int *a, int low, int high, int mid,int max)
{
   int i, j, k; 
   int *c=new int[max];   //error occurs here
   i = low;
   k = low;
   j = mid + 1;
   while (i <= mid && j <= high)
   {
       if (a[i] < a[j])
       {
           c[k] = a[i];
           k++;
           i++;
       }
       else
       {
           c[k] = a[j];
           k++;
           j++;

       }
   }
   while (i <= mid)
   {
       c[k] = a[i];

       k++;
       i++;
   }
   while (j <= high)
   {
       c[k] = a[j];
       k++;
       j++;
   }
   for (i = low; i < k; i++)
   {
       a[i] = c[i];
   }
}

错误截图

什么问题，好像没有更多可用内存了？？

4

1 回答 1

1

你的腐败问题是这样的：

k = low;

您正在k用作临时数组的索引。它应该从 0 开始，而不是low更改为：

k = 0;

关于算法的其余部分，您有明显的内存泄漏。你没有删除你的临时数组。此外，归并排序算法在 C 和 C++ 中比大多数语言更容易，这正是因为它具有指针算术的本机能力

例如：

template<typename T>
void merge(T* ar, size_t mid, size_t len)
{
    T *merged = new T[len]; // note. normally i would use a smart pointer

    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            merged[k++] = ar[i++];
        else
            merged[k++] = ar[j++];
    }

    while (i < mid)
        merged[k++] = ar[i++];
    while (j < len)
        merged[k++] = ar[j++];

    std::copy(merged, merged+k, ar);
    delete [] merged;
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    mergesort(ar, len/2);
    mergesort(ar+len/2, len-len/2);
    merge(ar, len/2, len);
}

使用上述。下面演示了它是如何被调用的：

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

    std::vector<int> data;
    data.reserve(25);
    std::generate_n(std::back_inserter(data), data.capacity(),
                    [&](){ return dist(rng);});

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    mergesort(data.data(), data.size());

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

输出（明显不同）

55 39 40 87 49 1 94 8 20 47 42 23 93 99 81 52 17 66 3 6 74 5 49 13 67 
1 3 5 6 8 13 17 20 23 39 40 42 47 49 49 52 55 66 67 74 81 87 93 94 99

所有这一切都说，除非这是为了学术界，否则你疯了不只是使用std::sort

替代分配

自下而上的设计在不同的情况下效果很好，但它使用的内存分配系统对于大型集合来说是可怕的。所需的总临时空间永远不会超过-item 容器N的项目N，因此您可以使用前端加载器将其预先分配给实际的合并排序，然后与合并算法一起提供临时空间以供使用而不是自己分配。唯一棘手的部分是知道在 tmp 存储中可以安全使用空间的位置。但你已经知道了。您用于排序序列的相同偏移量也可用于正确匹配的临时空间位置：

template<typename T>
void merge(T* ar, size_t mid, size_t len, T* tmp)
{
    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            tmp[k++] = ar[i++];
        else
            tmp[k++] = ar[j++];
    }

    while (i < mid)
        tmp[k++] = ar[i++];
    while (j < len)
        tmp[k++] = ar[j++];

    std::copy(tmp, tmp+k, ar);
}


template<typename T>
void mergesort_int(T* ar, size_t len, T* tmp)
{
    if (len < 2)
        return;

    mergesort_int(ar, len/2, tmp);
    mergesort_int(ar+len/2, len-len/2, tmp+len/2);
    merge(ar, len/2, len, tmp);
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    std::vector<T> tmp(len)
    mergesort_int(ar, len, &tmp[0]);
}

使用上main()一个示例中的相同，结果是相似的：

24 9 26 93 35 75 99 95 49 58 32 37 30 88 55 13 76 23 99 90 50 66 38 8 3 
3 8 9 13 23 24 26 30 32 35 37 38 49 50 55 58 66 75 76 88 90 93 95 99 99

请记住，这现在需要一个单独的分配N项（在我们的例子中，我们使用一个向量进行自动内存管理），然后在整个算法中使用它。您会发现这要快得多，尤其是对于大型数据集。

于 2014-03-12T08:44:58.273 回答