合并排序不能完全工作

Question

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

#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

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

Answer 2

输入的合并需要进行排序阵列，菲利普前面提到的。 Mergesort是递归的。为此，需要对它们进行分割，直到达到数组中只有一个元素的位置（因此它被排序）并合并所有数组以成为输入的排序结果。维基百科是你的朋友，以了解算法：Mergesort

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

Answer 3

传统上，递归调用merge_sort是为了对每个子范围进行排序，直到子范围只有一长为止，然后将它们合并在一起。

在你mergesort，b需要的a第一n/2值，即5和4 c取剩余值3,2,1。

你再调用merge（BTW你为什么传递a[]这样做呢？它不使用） 第一个循环

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

将有n2 = 2和n-n2 = 5-2 = 3 这使得3在启动以来b[0]>c[0]=3和自b[1]>c[1]=2以及d[2]之后的第二个出于类似原因。 既然你不递减，你不会对这些进行排序。 然后，您完成了小于n2的i = 0的while循环。 你刚才说

if(i<n2) 

，所以你刚刚从B的是5

复制的第一件事，所有这给3，2，1，5和0，因为你做d全球。

Answer 4

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

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

#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; 
    } 
} 

Answer 5

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); 
}