合并排序实现未按预期工作

Question

我一直在尝试实现归并排序；但不知何故实现是不正确的——输出包含不属于原始数组的值。我试过将它与其他人的实施（工作）进行比较，但似乎找不到错误。

密码是：-

#include <iostream>

using namespace std;
void Merge (int A[], int lo, int hi, int mid){
    int i = lo;
    int k = 0;
    int j = mid+1;
    int R[hi-lo];

    while(i<=mid && j<=hi){
        if(A[i]<A[j]){
            R[k]=A[i];
            cout << A[i] << "; " << A[j] << "      " << i << "        " << j << endl;
            i++;
        }else {
            R[k]=A[j];
            cout << A[i] << "; " << A[j] << "      " << i << "        " << j << endl;
            j++;
        }k++;
    }
    while(i<=lo){
        R[k]=R[i];
        i++;k++;
    }
    while(j<=hi){
        R[k]=R[j];
        j++;k++;
    }
    int count =0;
    for(i=lo; i<hi; i++){
        A[i]=R[count];
        count++;
        cout << count << "    ;    " << i << "-/-/-/-/-/-/-" << flush;
    }
}
void mergeSort(int A[], int lo, int hi){
    //if(hi-lo+1<2)return;
    if (lo<hi){
    int mid = (lo+hi)/2;
    mergeSort(A, lo, mid);
    mergeSort(A, mid+1, hi);
    Merge (A, lo, hi, mid);}
}

int main(){
    int A[] = {1,5,3,4,8,9,150,7,51,65};
    int hi = sizeof(A)/sizeof(int);
    cout << hi << endl;
    mergeSort(A,0, hi);
    cout << endl << endl << endl << endl;
    for(int i=0; i<=hi; i++){
        cout<<A[i]<< "; " << flush;
    }
    return 0;
}

我试图搜索类似的 Q(S)，但找不到。

Answer 1

您的实施问题是边界包含和错误数组的混合。

首先，查看合并中最后的 2 个 while 循环，您做了：R[k]=R[i];当您的意思是 R[k]=A[i];

在同一个函数上，你的 for 循环缺少一个迭代，循环守卫应该是 i<=hi 而不是 i<hi。

hi的初始化也是错误的，因为你初始化的是元素个数而不是最后一个索引，你应该减去-1。

我也不知道你的打印代码在做什么，所以我注释掉并添加了我自己的代码，我发现它更清楚。

我更正了你的代码如下：

   #include <iostream>

using namespace std;
void Merge (int A[], int lo, int hi, int mid){
    int i = lo;
    int k = 0;
    int j = mid+1;
    int R[hi-lo];

    cout << "input" << endl;
    for(int i=lo; i<=mid; i++)
        cout << A[i] << " ";
    cout << endl;
    for(int i=mid+1; i<=hi; i++)
        cout << A[i] << " ";

    cout << endl;

    while(i<=mid && j<=hi){
        if(A[i]<A[j]){
            R[k]=A[i];
            //cout << A[i] << "; " << A[j] << "      " << i << "        " << j << endl;
            i++;
        }else {
            R[k]=A[j];
            //cout << A[i] << "; " << A[j] << "      " << i << "        " << j << endl;
            j++;
        }k++;
    }
    while(i<=mid){
        R[k]=A[i];
        i++;k++;
    }
    while(j<=hi){
        R[k]=A[j];
        j++;k++;
    }
    int count =0;
    for(i=lo; i<=hi; i++){
        A[i]=R[count];
        count++;
        //cout << count << "    ;    " << i << "-/-/-/-/-/-/-" << flush;
    }

    cout << "output:" << endl;
    for(int i=lo; i<=hi; i++)
        cout << A[i] << " ";
    cout << endl;
}
void mergeSort(int A[], int lo, int hi){
    //if(hi-lo+1<2)return;
    if (lo<hi){
    int mid = (lo+hi)/2;
    mergeSort(A, lo, mid);
    mergeSort(A, mid+1, hi);
    Merge (A, lo, hi, mid);}
}

int main(){
    int A[] = {1,5,3,4,8,9,150,7,51,65};
    int hi = sizeof(A)/sizeof(int) -1;
    cout << hi << endl;
    mergeSort(A,0, hi);
    cout << endl << endl << endl << endl;
    for(int i=0; i<=hi; i++){
        cout<<A[i]<< "; " << flush;
    }
    return 0;
}

合并排序实现未按预期工作

Merge Sort implementation not working as expected

c++

sorting

mergesort

c++14