我的合并排序实现 C++ 中的问题

Question

我一直在学习归并排序算法，但遇到了一些麻烦。在我的实现中，输出中的一些数字丢失了，而另一些则重复了。我正在使用向量并遵循 Cormen 等人在算法简介中描述的算法。阿尔。和 Geeksforgeeks.

代码如下：

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

void merge_sort(vector<int>&, int, int);
void merge(vector<int>&, int, int, int);

int main() {
    
    vector<int> A = {5, 2, 4, 6, 1, 3};
    int p = 0;
    int r = A.size() - 1;
    
    merge_sort(A, p, r);
    
    for(int num : A)
        cout << num << " ";
    
    return 0;
}

void merge_sort(vector<int>&A, int p, int r){
    if(p >= r)
        return;
    
    int mid = (p+r)/2;
    merge_sort(A, p, mid);
    merge_sort(A, mid+1, r);
    merge(A, p, mid, r);
}

void merge(vector<int>&A, int p, int mid, int r){
    int numLeft = mid - p + 1;
    int numRight = r - mid;
    
    //create two new vectors
    vector<int> left;
    vector<int> right;
    
    //copy elements over
    for(int i = 0; i < numLeft; i++)
        left.push_back(A[i]);
    for(int j = mid+1; j < (mid+1+numRight); j++)
        right.push_back(A[j]);
    
    //compare elements from the two arrays     
    int i = 0;
    int j = 0;
    int k = 0;
    
    while(i < numLeft && j < numRight){
        if(left[i] <= right[j]){
            A[k] = left[i];
            i++;
        }
        else{
            A[k] = right[j];
            j++;
        }
        k++;
    }
    //check if one half terminated before the other
    while(i < numLeft){
        A[k] = left[i];
        k++; i++;
    }
    while(j < numRight){
        A[k] = right[j];
        k++; j++;
    }
}

输出：1 2 3 6 1 3

Answer 1

您的 merge 函数假定您使用 p=0 进行排序。您应该从 p 复制，而不是从 0 复制。然后从 p:

开始用 k 放回去

    //copy elements over
    for (int i = p; i < p + numLeft; i++)
        left.push_back(A[i]);
    for (int j = mid + 1; j < (mid + 1 + numRight); j++)
        right.push_back(A[j]);

    //compare elements from the two arrays     
    int i = 0;
    int j = 0;
    int k = p;

我的合并排序实现 C++ 中的问题

Problem in My Merge Sort Implementation C++

c++

algorithm

mergesort