1

我正在尝试为合并排序编写代码。我没有得到正确的输出。我正在关注这个伪代码链接以下是我的代码。我将未排序的数组传递给merge_sort函数并递归调用merge函数对子数组进行排序和组合。我知道有更简单有效的方法来编写合并排序的代码，但我想自己尝试，否则我不会学习. 提前致谢。

int* merge_sort(int* a,int size)
{
    //cout<<size;
    //cout<<"hi";
    if(size == 1)
    {
        //cout<<"less";
        //cout<<a[0];

        return a;

    }
    int* left;
    int* right;

        int middle = ceil(size/2);
        left = new int(middle);
        right = new int(middle);
        for(int i=0;i<middle;i++)
        {
            left[i]=a[i];
            //cout<<left[i];
        }
        cout<<"\t";

        for(int j=middle;j<size;j++)
        {
            right[j]=a[j];
            //cout<<right[j];
        }
        cout<<"\t";
        left = merge_sort(left,middle);
        //if(size==2)
            //cout<<left[0];

        right = merge_sort(right,middle);
        //if(size==2)
            //cout<<right[0];

        return merge(left,right,middle);


}




int* merge(int* l,int* r,int m)
    {
        int* result;
        result = new int(2*m); //to store the output
        int lsize=m;  // to keep track of left sub list
        int rsize=m;  // to keep track of right sub list
        int counter = 0;  // will use to index result
        //cout<<m;


        while(lsize>0 || rsize>0)
        {
            if(lsize>0 && rsize>0)
            {
                if(l[0]<=r[0])
                {
                    result[counter]=l[0];
                    counter++; //to store next value in result
                    lsize--;  
                    l=&l[1]; //decrementing the size of left array
                }
                else
                {
                    result[counter]=r[0];
                    counter++;
                    rsize--; 
                    r=&r[1]; //dec. size of right array
                }

            }
            else if(lsize>0)
            {
                result[counter]=l[0];
                counter++;
                lsize--;
                l=&l[1];
            }
            else if(rsize>0)
            {
                result[counter]=l[0];
                counter++;
                lsize--;
                l=&l[1];
            }

        }
            return result;
    }
4

1 回答 1

3

你的代码：

int *left = new int(middle);

分配一个初始化为 的整数middle。你需要：

int *left = new int [middle];

它分配一个middle整数数组。冲洗并重复int *right。实际上，您需要使用：

int *right = new int [size - middle];

这将获得right数组的正确大小。然后，您必须修改对子数组merge_sort()的递归调用：right

merge_sort(right, size - middle);

最后，您必须重写merge()以独立获取左侧数组的大小和右侧数组的大小，因为它们可能具有不同的大小。例如，如果您对 10 个元素进行排序，那么您最终会调用合并两个 5 的数组（这很好），但在下一个级别，您需要合并一个 2 的数组和一个 3 元素的数组（并且您'被冲洗）。

的分配result也有()vs[]分配的问题。还有一些其他尚未解决的问题。但这些都是朝着正确方向迈出的重要一步。

正如对该问题的评论中所提到的，您也有一个巨大的内存泄漏问题。更何况修复也不是小事，因为merge_sort()提前退出不分配新内存，所以没有‘删除返回的内存’这么简单merge_sort()。

复制和粘贴非常棒，直到您忘记正确编辑粘贴的副本：

    else if (lsize > 0)
    {   
        result[counter] = l[0];
        counter++;
        lsize--;
        l = &l[1];
    }   
    else if (rsize > 0)
    {   
        result[counter] = l[0];
        counter++;
        lsize--;
        l = &l[1];
    }

我认为你应该在这些块的第二个中使用r和rsize。

这还不是故事的全部……

并且剩余的问题（除了内存管理，它仍然是 100% 泄漏和有问题的）是：

    for(int j=middle;j<size;j++)
    {
        right[j]=a[j];
        //cout<<right[j];
    }

您正在复制到right您尚未分配的部分。你需要更多类似的东西：

    for(int j = 0; j < size - middle; j++)
    {
        right[j] = a[j + middle];
        //cout<<right[j];
    }

只要您始终在顶层对至少两个项目进行排序，此代码就可以工作（如果您对 1 个项目进行排序，则会崩溃释放未分配的空间——这是内存管理问题的一部分）。

#include <iostream>
using namespace std;

namespace {

int *merge(int *l, int m, int *r, int n);

void dump_array(int *a, int size)
{
    int i;
    cout << size << ": ";
    for (i = 0; i < size; i++)
    {
        cout << ' ' << a[i];
        if (i % 10 == 9)
            cout << '\n';
    }
    if (i % 10 != 0)
        cout << '\n';
}

};

int *merge_sort(int *a, int size)
{
    cout << "-->> merge_sort:\n";
    dump_array(a, size);
    if (size <= 1)
    {
        cout << "<<-- merge_sort: early return\n";
        return a;
    }

    int middle = size/2;
    int *left = new int[middle];
    int *right = new int[size - middle];
    cout << middle << ": ";
    for (int i = 0; i < middle; i++)
    {
        left[i] = a[i];
        cout << ' ' << left[i];
    }
    cout << "\n";

    cout << (size - middle) << ": ";
    for (int j = 0; j < size - middle; j++)
    {
        right[j] = a[j + middle];
        cout << ' ' << right[j];
    }
    cout << "\n";
    cout << "MSL:\n";
    int *nleft = merge_sort(left, middle);
    cout << "NL: ";
    dump_array(nleft, middle);
    cout << "OL: ";
    dump_array(left, middle);
    cout << "OR: ";
    dump_array(right, size - middle);
    cout << "MSR:\n";
    int *nright = merge_sort(right, size - middle);
    cout << "NR: ";
    dump_array(nright, size - middle);
    cout << "NL: ";
    dump_array(nleft, middle);
    cout << "OL: ";
    dump_array(left, middle);
    cout << "OR: ";
    dump_array(right, size - middle);
    int *result =  merge(nleft, middle, nright, size - middle);
    cout << "<<-- merge_sort:\n";
    dump_array(result, size);
    return result;
}

namespace {

int *merge(int *l, int m, int *r, int n)
{
    int *result = new int[m + n];
    int lsize = m;
    int rsize = n;
    int counter = 0;
    cout << "-->> merge: (" << m << "," << n << ")\n";
    dump_array(l, m);
    dump_array(r, n);

    while (lsize > 0 || rsize > 0)
    {
        if (lsize > 0 && rsize > 0)
        {
            if (l[0] <= r[0])
            {
                result[counter] = l[0];
                cout << "C: " << counter << "; L = " << l[0] << "; LS = " << lsize << '\n';
                counter++;
                lsize--;
                l++;
            }
            else
            {
                result[counter] = r[0];
                cout << "C: " << counter << "; R = " << r[0] << "; RS = " << rsize << '\n';
                counter++;
                rsize--;
                r++;
            }
        }
        else if (lsize > 0)
        {
            result[counter] = l[0];
            cout << "C: " << counter << "; L = " << l[0] << "; LS = " << lsize << '\n';
            counter++;
            lsize--;
            l++;
        }
        else if (rsize > 0)
        {
            result[counter] = r[0];
            cout << "C: " << counter << "; R = " << r[0] << "; RS = " << rsize << '\n';
            counter++;
            rsize--;
            r++;
        }
    }
    cout << "<<-- merge:\n";
    dump_array(result, m+n);
    return result;
}

};

int main()
{
    for (int i = 2; i <= 10; i++)
    {
        int array1[] = { 9, 3, 5, 7, 1, 8, 0, 6, 2, 4 };
        cout << "\nMerge array of size " << i << "\n\n";
        int *result = merge_sort(array1, i);
        delete[] result;
    }
    return 0;
}

这是充满调试的代码。这是我得到结果的水平。我也许可以使用调试器。如果我在一台可以valgrind工作的机器上，它可能也有帮助（但遗憾的是，它在 Mac OS X 10.8.x 上不起作用）。

仍然有很多很多方法可以改进代码——包括内存管理。您可能会发现最简单的方法是将输入数组传递给merge()用作结果数组（避免该代码中的内存分配）。这将减少内存管理负担。

当您删除调试代码时，您需要dump_array()在程序中调用该函数main()来获取排序前后的数组图像。

代码转换为模板函数且无泄漏

我已经相当简化了代码，尤其是在merge()函数中。此外，出于好奇，将其转换为一组模板函数，然后将它们与 4 种不同的数组类型 ( int, double, std::string, char) 一起使用。调试量大大减少，主要调试条件是-DTRACE_ENABLED现在编译。

代码现在没有泄漏；valgrind如果没有例外，在 Linux 机器（虚拟机）上会给它一个干净的健康单。但是，不能保证异常安全。事实上，考虑到 and 的直接使用，new几乎delete可以保证它不是异常安全的。我已经把namespace控制留在原地，但我远不能相信它真的是正确的——事实上，我认为它不好。（我也很好奇是否有人对如何在namespace {…};块内布局代码有任何看法；不缩进一组大括号内的所有内容似乎很奇怪，但是…）

#include <iostream>
using namespace std;

namespace {

#if !defined(TRACE_ENABLED)
#define TRACE_ENABLED 0
#endif

enum { ENABLE_TRACE = TRACE_ENABLED };

template <typename T>
void merge(T *l, int m, T *r, int n, T *result);

template <typename T>
void dump_array(const char *tag, T *a, int size)
{
    int i;
    cout << tag << ": (" << size << ") ";
    for (i = 0; i < size; i++)
    {
        cout << "  " << a[i];
        if (i % 10 == 9)
            cout << '\n';
    }
    if (i % 10 != 0)
        cout << '\n';
}

};

template <typename T>
void merge_sort(T *a, int size)
{
    if (size <= 1)
        return;

    if (ENABLE_TRACE)
        dump_array("-->> merge_sort", a, size);
    int middle = size/2;
    T *left = new T[middle];
    T *right = new T[size - middle];

    for (int i = 0; i < middle; i++)
        left[i] = a[i];

    for (int j = 0; j < size - middle; j++)
        right[j] = a[j + middle];

    merge_sort(left, middle);
    merge_sort(right, size - middle);
    merge(left, middle, right, size - middle, a);
    delete [] left;
    delete [] right;
    if (ENABLE_TRACE)
        dump_array("<<-- merge_sort", a, size);
}

namespace {

template <typename T>
void merge(T *l, int m, T *r, int n, T *result)
{
    T *l_end = l + m;
    T *r_end = r + n;
    T *out = result;
    if (ENABLE_TRACE)
    {
        cout << "-->> merge: (" << m << "," << n << ")\n";
        dump_array("L", l, m);
        dump_array("R", r, n);
    }

    while (l < l_end && r < r_end)
    {
        if (*l <= *r)
            *out++ = *l++;
        else
            *out++ = *r++;
    }
    while (l < l_end)
        *out++ = *l++;
    while (r < r_end)
        *out++ = *r++;

    if (ENABLE_TRACE)
        dump_array("<<-- merge", result, m+n);
}

};

#include <string>

int main()
{

    for (size_t i = 1; i <= 10; i++)
    {
        int array1[] = { 9, 3, 5, 7, 1, 8, 0, 6, 2, 4 };
        if (i <= sizeof(array1)/sizeof(array1[0]))
        {
            cout << "\nMerge array of type int of size " << i << "\n\n";
            dump_array("Original", array1, i);
            merge_sort(array1, i);
            dump_array("PostSort", array1, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        double array2[] = { 9.9, 3.1, 5.2, 7.3, 1.4, 8.5, 0.6, 6.7, 2.8, 4.9 };
        if (i <= sizeof(array2)/sizeof(array2[0]))
        {
            cout << "\nMerge array of type double of size " << i << "\n\n";
            dump_array("Original", array2, i);
            merge_sort(array2, i);
            dump_array("PostSort", array2, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        std::string array3[] = { "nine", "three", "five", "seven", "one", "eight", "zero", "six", "two", "four" };
        if (i <= sizeof(array3)/sizeof(array3[0]))
        {
            cout << "\nMerge array type std::string of size " << i << "\n\n";
            dump_array("Original", array3, i);
            merge_sort(array3, i);
            dump_array("PostSort", array3, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        char array4[] = "jdfhbiagce";
        if (i <= sizeof(array4)/sizeof(array4[0]))
        {
            cout << "\nMerge array type char of size " << i << "\n\n";
            dump_array("Original", array4, i);
            merge_sort(array4, i);
            dump_array("PostSort", array4, i);
        }
    }

    return 0;
}
于 2013-09-21T04:35:51.143 回答