0

在阅读了 TopCoder 上的 Merge Sort 理论后，我尝试编写它的实现，但它变得越来越奇怪，而且我或多或少是编程的初学者，尤其是算法。有人可以帮助我吗？

    #include <iostream>
using namespace std;

int arr[] = {2, 0, 43, 12, 98};

int sizeOfarr(int a[])
{
    return sizeof(a)/sizeof(a[0]);
}

int minElement(int x, int y)
{
    if (x > y)
    {
        return y;
    }
    else if (x < y)
    {
        return x;
    }
    else
    {
        return x, y;
    }
}

int main()
{
    int t, z;
    int n = sizeOfarr(arr);
    int finalList[n];
    int list1[n];
    int list2[n];
    for(int i = 0; i<=((n/2)-1); i++)
    {
        list1[i] = arr[i];
    }
    for(int j = n/2; j<n; j++)
    {
        for(int k = 0; k<=((n/2)-1); k++ )
        {
            list2[k] = arr[j];
        }
    }
    for(int y = 0; y<=n; y++)
    {
        while(sizeOfarr(finalList)!=n)
        {
            t = list1[0];
            z = list2[0];
            finalList[y] = minElement(t, z);
            if(finalList[y]==t)
            {
                list1[0] = list1[1];
            }
            else if(finalList[y]==z)
            {
                list2[0] = list2[1];
            }
            else
            {
                list1[0] = list1[1];
                list2[0] = list2[1];
            }
        }
    }
    cout << "The sorted list is: " << finalList << endl;
    return 0;
}
4

2 回答 2

2 
#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;
int temp[10000];

void merge(int *A,int low,int mid,int high)
{
    int i=low;
    int j=mid+1;
    int k=low;
    int l;

    while(i<=mid && j<=high)
    {
        if(A[i]<A[j])
        {
            temp[k]=A[i];
            i=i+1;
        }
        else
        {
            temp[k]=A[j];
            j=j+1;
        }
        k++;
    }
    for(l=i;l<=mid;l++,k++)
    {
        temp[k]=A[l];
    }
    for(l=j;l<=high;l++,k++)
    {
        temp[k]=A[l];
    }
    memcpy(A,temp,sizeof(A[0])*k);
}

void mergeSort(int *A,int low,int high)
{
    int mid;
    if(low<high)
    {
        mid=floor((low+high)/2);
        mergeSort(A,low,mid);
        mergeSort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}

int main(int argc,char *argv[])
{
    int n;
    int array[10000];
    cout<<"please enter the number numbers\n";
    cin>>n;
    cout<<"please enter the nubers\n";
    for(int i=0;i<n;i++)
    {
        cin>>array[i];
    }
    mergeSort(array,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<array[i]<<"   ";
    }
    cout<<"\n";
}

这是我的实现 mergeSort 函数在中间递归划分并重复直到低 lt（小于）高，然后调用合并函数。

我从您的代码中看到运算符“，”（返回 x，y）将用 y 值替换 x 值。

于 2013-08-04T08:44:20.793 回答
1

对代码的几点评论：

return x,y // 这只是返回 y。当 x==y 时就是这种情况，所以它可能是好的，而不是一个人会写的。

while(sizeOfarr(finalList)!=n) // 你的数组 finalist 的大小是 n 个元素。这永远不会改变，所以这个 while 条件总是错误的，循环永远不会执行。

于 2013-08-04T08:42:16.190 回答