0

下面给出了我为合并排序所做的代码。问题是，在给出输入时，输出是3 2 1 5 0。出了什么问题？

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

int d[100];

void merge(int a[], int b[], int c[], int n)
{
int n2=floor(n/2);
int i=0, j=0, k=0;
while(i<n2 && j<(n-n2))
{
    if(b[i]<c[j])
    {
        d[k++]=b[i++];
    }
    else if(b[i]>c[j])
    {
        d[k++]=c[j++];
    }
}
    if(i==n2)
    {
        if(j<(n-n2))
        {
            d[k++]=c[j++];
        }
    }
    if(i<n2)
    {
        d[k++]=b[i++];
    }
}


void mergesort(int a[], int n)
{
int n2=floor(n/2);
int b[50],c[50];
int i,j=0,k=0;
for(i=0;i<n2;i++)
{
    b[i]=a[k++];
}
while(k<n)
{
    c[j++]=a[k++];
}
merge(a,b,c,n);
}

int main()
{
int a[]={5,4,3,2,1};
int n=5;
mergesort(a,n);
for(int i=0;i<n;i++)
{
    cout<<d[i]<<endl;
}
}
4

5 回答 5

4

主要问题是传递给合并的数组（b 和 c）没有排序。其他问题是该算法不是递归的，并且合并并不总是将 b 和 c 中的所有数字放入 a。

一个似乎对您的代码更改最少的版本将是

void merge(int a[], int b[], int c[], int n)
{
  int n2=floor(n/2);
  int i=0, j=0, k=0;
  while(k<n)
  {
    if((j == (n-n2) || b[i]<c[j]) && i < n2)
    {
      a[k++]=b[i++];
    }
    else
    {
      a[k++]=c[j++];
    }
  }
}


void mergesort(int a[], int n)
{
  int n2=floor(n/2);
  int b[50],c[50];
  int i,j=0,k=0;
  for(i=0;i<n2;i++)
  {
    b[i]=a[k++];
  }
  while(k<n)
  {
    c[j++]=a[k++];
  }
  if(n2 > 1) {
    mergesort(b, n2);
  }
  if(n - n2 > 1) {
    mergesort(c, n - n2);
  }
  merge(a,b,c,n);
}

int main()
{
  int a[]={5,4,3,2,1};
  int n=5;
  mergesort(a,n);
  for(int i=0;i<n;i++)
  {
    cout<<a[i]<<endl;
  }
}
于 2013-07-31T07:18:39.383 回答
2

通常递归调用 merge_sort 以便对每个子范围进行排序，直到子范围只有一个长，然后将它们合并在一起。

在您的mergesort中，b取 的前 n/2 个值a，即 5 和 4。 c取其余值 3、2、1。

然后你调用merge（顺便说一句，你为什么要传递a[]给这个？它没有被使用）第一个循环

while(i<n2 && j<(n-n2))

将有n2 = 2andn-n2 = 5-2 = 3 这将 3 放在 start sinceb[0]>c[0]=3和 2 next sinceb[1]>c[1]=2和 1 atd[2]出于类似的原因。由于您不递归，因此您不会对这些进行排序。然后用小于 n2 的 i = 0 完成 while 循环。你就说

if(i<n2)

所以你只需从 b 复制第一件事，即 5。

所有这一切都给出了 3、2、1、5 和 0，因为您将其设为d全局。

于 2013-07-31T07:41:40.630 回答
1

正如 Philip 之前提到的，merge 的输入需要排序数组。合并排序是递归的。为此，您需要将它们分开，直到到达数组中只有一个元素（因此已排序）的点，然后合并所有数组以成为输入的排序结果。维基百科是你理解算法的朋友：Mergesort

顺便说一句：您需要确保合并检查中比较的两种情况之一也检查值的相等性。

于 2013-07-31T07:39:00.147 回答
0 
template <typename T>
void merge(T arr[], int begin, int mid, int end)
{
    int len = end - begin;
    T *temp = new T[len];
    int i = begin;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end)
    {
        if(arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid)
        temp[k++] = arr[i++];
    while(j <= end)
        temp[k++] = arr[j++];

    memcpy(arr + begin, temp, len*sizeof(T));
    delete []temp;
}
template <typename T>
void mergeSort(T arr[], int begin, int end)
{
    if (begin >= end)
        return;

    int mid = (end + begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
}
于 2013-07-31T09:23:33.437 回答
0

菲利普是对的，您的代码中根本没有递归。

但是，还有一些错误。我已经用注释标记了它，就像菲利普的后记一样。

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

int d[100];

void merge(int a[], int b[], int c[], int n)
{
    int n2=floor(n/2);
    int i=0, j=0, k=0;
    while(i<n2 && j<(n-n2))
    {
        if(b[i]<c[j])
        {
            d[k++]=b[i++];
        }
        else if(b[i]>c[j])
        {
            d[k++]=c[j++];
        }
        /***************************************************/
        /* What if b[i] == c[j] here?                      */
        /* Your code will drop into an infinity loop.      */
        /***************************************************/
    }
    if(i==n2)
    {
        if(j<(n-n2))
        /****************************************************/
        /* Use **while** here?                              */
        /* Because there may be more than one elements left */
        /* in c[].                                          */
        /****************************************************/
        {
            d[k++]=c[j++];
        }
    }
    if(i<n2)
    /***************************************************/
    /* Use **while** here? - With the same reason      */
    /***************************************************/
    {
        d[k++]=b[i++];
    }
}


void mergesort(int a[], int n)
{
    int n2=floor(n/2);
    int b[50],c[50];
    int i,j=0,k=0;
    for(i=0;i<n2;i++)
    {
        b[i]=a[k++];
    }
    while(k<n)
    {
        c[j++]=a[k++];
    }
    merge(a,b,c,n);
}

int main()
{
    int a[]={5,4,3,2,1};
    int n=5;
    mergesort(a,n);
    for(int i=0;i<n;i++)
    {
        cout<<d[i]<<endl;
    }
}
于 2013-07-31T08:52:41.423 回答