合并排序 C++ 代码 returns 相同顺序的数字且不排序

Question

代码：

// Merge sort
#include <iostream>
#include <algorithm>
using namespace std;

void Merge(int *A, int *B1, int one, int *B2, int two){
    int *combi = new int[one+two];
    int c = 0, d = 0, x=0;
    while(c < one && d < two){
        cout<<"B1[C] "<<B1[c]<<" B2[d] "<<B2[d]<<endl;
        if(B1[c] < B2[d]){
            combi[x] = B1[c];
            cout<<"combi[x] = "<<combi[x]<<endl;
            c++;
        }
        else{
            combi[x] = B2[d];
            cout<<"combi[x] = "<<combi[x]<<endl;
            d++;
        }
        x++;
    }
    while(c < one){
        combi[x] = B1[c];
        x++;
        c++;
    }
    while(d < two){
        combi[x] = B2[d];
        x++;
        d++;
    }
    

    cout<<"combi is ";
    for(int f = 0; f<one+two; f++) cout<<combi[f]<<' ';
    cout<<endl<<endl;
    
}

void MergeSort(int *A, int n){
    if (n > 1){
        int *B1 = new int[n/2];
        int *B2 = new int[n - n/2];

        for(int x = 0; x < n/2; x++){B1[x] = A[x];}
        for(int x = 0; x < n - n/2; x++){B2[x] = A[x + n/2];}

        cout<<endl<<"B1 is ";
        for(int x = 0; x < n/2; x++)cout<<B1[x]<<' ';
        cout<<endl<<"B2 is ";

        for(int x = 0; x < n - n/2; x++)cout<<B2[x]<<' ';
        cout<<endl;

        MergeSort(B1, n/2);
        MergeSort(B2, n - n/2);

        Merge(A, B1, n/2, B2, n - n/2);
    }
}

int main() {
    int A[ ] = {4,2,6,1};
    MergeSort(A, 4);
    cout<<endl<<endl<<"final A: "<<endl;
    for (int i=0; i < 4; i++) cout << A[i] << " ";
    return 0;
}

输出：

B1 is 4 2 
B2 is 6 1 

B1 is 4 
B2 is 2 
B1[C] 4 B2[d] 2
combi[x] = 2
combi is 2 4 


B1 is 6 
B2 is 1 
B1[C] 6 B2[d] 1
combi[x] = 1
combi is 1 6 

B1[C] 4 B2[d] 6
combi[x] = 4
B1[C] 2 B2[d] 6
combi[x] = 2
combi is 4 2 6 1 



final A: 
4 2 6 1

如您所见，代码一开始运行很流畅，对 4 2 和 6 1 进行了排序。但是，这种排序似乎只是暂时的，因为当 B1 和 B2 之后尝试合并时，它们最终变得相同数如前。这和我使用指针有关系吗？

输出中的“combi is 1 6”行之后的代码似乎乱七八糟。有谁知道发生了什么以及如何解决这个问题？

Answer 1

您的代码 Merge 有问题。在函数入口你期望合并后的数组写在参数A中，但实际上它写在局部变量combi中，你没有在任何地方使用它，因此它不影响结果

要解决此问题只需在Merge函数中将变量combi的每次调用替换为调用A.

结果应该是这样的。注意：我还添加了释放内存，但总的来说我没有让代码更干净

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

void Merge(int *A, int *B1, int one, int *B2, int two){
    int c = 0, d = 0, x=0;
    while(c < one && d < two){
        cout<<"B1[C] "<<B1[c]<<" B2[d] "<<B2[d]<<endl;
        if(B1[c] < B2[d]){
            A[x] = B1[c];
            cout<<"combi[x] = "<<A[x]<<endl;
            c++;
        }
        else{
            A[x] = B2[d];
            cout<<"combi[x] = "<<A[x]<<endl;
            d++;
        }
        x++;
    }
    while(c < one){
        A[x] = B1[c];
        x++;
        c++;
    }
    while(d < two){
        A[x] = B2[d];
        x++;
        d++;
    }
    

    cout<<"combi is ";
    for(int f = 0; f<one+two; f++) cout<<A[f]<<' ';
    cout<<endl<<endl;
    
}

void MergeSort(int *A, int n){
    if (n > 1){
        int *B1 = new int[n/2];
        int *B2 = new int[n - n/2];

        for(int x = 0; x < n/2; x++){B1[x] = A[x];}
        for(int x = 0; x < n - n/2; x++){B2[x] = A[x + n/2];}

        cout<<endl<<"B1 is ";
        for(int x = 0; x < n/2; x++)cout<<B1[x]<<' ';
        cout<<endl<<"B2 is ";

        for(int x = 0; x < n - n/2; x++)cout<<B2[x]<<' ';
        cout<<endl;

        MergeSort(B1, n/2);
        MergeSort(B2, n - n/2);

        Merge(A, B1, n/2, B2, n - n/2);

        delete[] B1;
        delete[] B2;
    }
}

int main() {
    int A[ ] = {4,2,6,1};
    MergeSort(A, 4);
    cout<<endl<<endl<<"final A: "<<endl;
    for (int i=0; i < 4; i++) cout << A[i] << " ";
    return 0;
}

P.S. 如果您的情况可用，您应该将代码从原始指针切换到 std::vector, from own Merge function to std::merge, from copying arrays elements by elements to std::copy

合并排序 C++ 代码 returns 相同顺序的数字且不排序

Merge sort c++ code returns same order of numbers and does not sort

c++

sorting

algorithm

mergesort