weixin_43653187
LostDog。
采纳率22.2%
2020-03-07 21:36 阅读 134

求问归并排序代码哪里有问题,请大家指教,谢谢!

代码如下所示:
测试后结果排序不正确,不知哪里写错了,请大家指教,谢谢

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

void mergeSort(int arr[], int L, int R);

int main( )
{
    int arr[6] = { 12,24,22,14,18,91 };
    mergeSort(arr, 0, 5);
    for (int i = 0;i < 6;i++)
    {
        printf_s("%d\n", arr[i]);
    }
}
//L和R都是index,注意
void merge(int arr[], int L, int M, int R)
{
    int Left_Size = M - L;
    int Right_Size = R - M + 1;
    //int Left[Left_Size];
    int* Left = (int*)malloc(sizeof(int) * Left_Size);
    if (Left == nullptr) { exit(-1); }
    int* Right = (int*)malloc(sizeof(int) * Right_Size);
    if (Right == nullptr) { exit(-1); }
    //int i; 
    for (int i = L;i < M;i++)
    {
        Left[i - L] = arr[i];
    }
    for (int i = M;i <= R;i++)
    {
        Right[i-M] = arr[i];
    }

    int i = 0,j = 0,k = L;
    while (i < Left_Size && j < Right_Size)
    {
        if (Left[i] < Right[i])
        {
            arr[k] = Left[i];
            i++;
            k++;
        }
        else
        {
            arr[k] = Right[j];
            j++;
            k++;
        }
    }
    while (i < Left_Size)
    {
        arr[k] = Left[i];
        i++;
        k++;
    }
    while (j < Right_Size)
    {
        arr[k] = Right[j];
        j++;
        k++;
    }

}
//L和R都是index,注意
void mergeSort(int arr[], int L,int R)
{
    if (L == R)
    {
        return;
    }
    else
    {
    int M = (L + R) / 2;
    mergeSort(arr, L, M);
    mergeSort(arr, M + 1, R);
    //这里第二个参数表示的是第二个数组第一个开头元素,所以我们要传入M+1
    merge(arr, L, M+1, R);
    }
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    weixin_43891765 格戮 2020-03-07 22:20

    你的代码中merge函数的while循环里,这个判断Right数组的下标错了,应该是Right[j]

     if (Left[i] < Right[i])
            {
                arr[k] = Left[i];
                i++;
                k++;
            }
    
    点赞 1 评论 复制链接分享
  • dabocaiqq dabocaiqq 2020-03-07 22:14

相关推荐