二路归并排序算法求解

Question

二路归并排序算法 不知道哪儿错了 结果不对 泪目

//二路归并排序
#include<stdio.h> 
#include<stdlib.h>
void printfX(int a[])//打印数组
{
    for(int i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    return;
}


void Merge(int a[],int low,int mid,int high)//左右分别有序，合成有序数组
{
    
    int *tmpa;
    int i=low;
    int j=mid+1;
    int k=0;

    tmpa=(int*)malloc((high-low+1)*sizeof(int));
    
     //核心逻辑：比较赋值给b[ ] 
     while(i<=mid&&j<=high)
     {
         if(a[i]<=a[j]){
             tmpa[k]=a[i];
             i++;
             k++;
         }
             
         else
             tmpa[k]=a[j];
             j++;
             k++;
     }
    while(i<=mid){
        tmpa[k]=a[i];
        k++;
        i++;
    }
        
    while(j<=high){
        tmpa[k]=a[j];
        k++;
        j++;
    }
         
    //回传值给b    
    for(k=0,i=low;i<=high;k++,i++)
    {
        a[i]=tmpa[k];
    }
    free(tmpa);
    
}


void mergesort(int a[],int low,int high) 
{
    int mid;
    if(low<high)
    {
        mid=(high+low)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
    return;
}


int main(){
    int a[]={2,5,1,7,10,6,9,4,3,8};
    mergesort(a,0,9);
    printfX(a);
    return 0;
}

Answer 1

引用 皆我百晓生 小程序回复内容作答：
在Merge函数中，当a[i]<=a[j]时，应该将a[i]赋值给tmpa[k]，然后i++和k++，而不是将a[j]赋值给tmpa[k]，然后j++和k++。

修改后的代码如下：

void Merge(int a[], int low, int mid, int high) {
    int *tmpa;
    int i = low;
    int j = mid + 1;
    int k = 0;

    tmpa = (int*)malloc((high - low + 1) * sizeof(int));

    while (i <= mid && j <= high) {
        if (a[i] <= a[j]) {
            tmpa[k] = a[i];
            i++;
            k++;
        }
        else {
            tmpa[k] = a[j];
            j++;
            k++;
        }
    }

    while (i <= mid) {
        tmpa[k] = a[i];
        k++;
        i++;
    }

    while (j <= high) {
        tmpa[k] = a[j];
        k++;
        j++;
    }

    for (k = 0, i = low; i <= high; k++, i++) {
        a[i] = tmpa[k];
    }

    free(tmpa);
}

通过这个修改，应该能得到正确的结果。