MKDLFDKFL 2022-09-30 15:43 采纳率: 50%
浏览 37
已结题

<算法导论第三版>的伪代码写的C++的归并排序

问题遇到的现象和发生背景

这是一个归并排序,是根据<算法导论第三版> 的伪代码写的,可是最终得到的结果总是错误的,不知道怎么回事总会访问到特定的数组外但是也没有发生编译过程的错误.

用代码块功能插入代码,请勿粘贴截图
我想要达到的结果
#include<iostream>
using namespace std;

void Merge(int *A,int p,int q,int r)
{
    int n1 = q - p;
    int n2 = r - q;
    
    cout << "q-p=" << q - p << endl;
    int* L = new int[n1+1];
    int* R = new int[n2];

    for (int i = 0; i <= n1; i++)
    {
        L[i] = A[p + i];
        
    }
    
    for (int j = 0; j < n2; j++)
    {
        R[j] = A[q + j + 1];
    }
    int i = 0;
    int j = 0;

    for (int k = p; k < r; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
                A[k] = R[j];
                j++;
        }
    }

}


void Merge_Sort(int* A, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = ((low + high) / 2);
        Merge_Sort(A, low, mid);
        Merge_Sort(A, mid + 1, high);
        Merge(A, low, mid, high);
    }

}


int main()
{
    int A[10] = {10,9,8,7,6,5,4,3,2,1};
    int low = 0;
    int high = 9;
    int mid = (low + high) / 2;
    Merge(A, low, mid, high);
    Merge_Sort(A, 0, 9);

    for (int m = 0; m < 10; m++)
    {
        cout << A[m] << " ";
    }

    cout << endl;
    
    return 0;
}

展开全部

  • 写回答

2条回答 默认 最新

  • _GX_ 2022-09-30 17:10
    关注

    你的merge代码没有考虑left和right数组元素数目不等的情况。

    #include <iostream>
    using namespace std;
    
    void Merge(int *A, int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
    
        int *L = new int[n1];
        int *R = new int[n2];
    
        for (int i = 0; i < n1; i++)
            L[i] = A[p + i];
    
        for (int j = 0; j < n2; j++)
            R[j] = A[q + j + 1];
    
        int i = 0;
        int j = 0;
        int k = p;
    
        // Merge L[] and R[] into A[]
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
                A[k++] = L[i++];
            else
                A[k++] = R[j++];
        }
        // Copy the remaining element of L[], if there are any
        while (i < n1)
            A[k++] = L[i++];
        // Copy the remaining element of R[], if there are any
        while (j < n2)
            A[k++] = R[j++];
    
        delete[] L;
        delete[] R;
    }
    
    void Merge_Sort(int *A, int low, int high)
    {
        int mid;
        if (low < high)
        {
            mid = (low + high) / 2;
            Merge_Sort(A, low, mid);
            Merge_Sort(A, mid + 1, high);
            Merge(A, low, mid, high);
        }
    }
    
    int main()
    {
        int A[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int low = 0;
        int high = 9;
        int mid = (low + high) / 2;
        Merge(A, low, mid, high);
        Merge_Sort(A, 0, 9);
    
        for (int m = 0; m < 10; m++)
        {
            cout << A[m] << " ";
        }
    
        cout << endl;
    
        return 0;
    }
    

    展开全部

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
    MKDLFDKFL 2022-10-02 01:27

    听君一席话,如拨云见日,茅塞顿开

    回复
查看更多回答(1条)
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 10月9日
  • 已采纳回答 10月2日
  • 创建了问题 9月30日
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部