合併排序不能完全工作

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