c++ - 合并排序不能完全工作

Question

我为归并排序编写的代码如下。问题是，在提供输入时，输出是 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;
}
}

Answer 1

主要问题是传递给 merge 的数组(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;
  }
}