c - 将合并操作的结果直接复制到辅助数组时，合并排序不起作用

Question

这是我用于归并排序的代码

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

int merge(int *arr,int *b,int low,int mid,int high)
{
    int i,j,k;
    i = low;
    j = mid+1;

//  printf("low: %d mid: %d high: %d\n",low,mid,high);
    for(k=low;k<=high;k++)
    {
        b[k] = arr[k];
    }
    k = low;
    while((i <= mid) && (j <= high))
    {
        if(b[i] <= b[j])
        {
            arr[k++] = b[i++];
        }
        else
        {
            arr[k++] = b[j++];
        }
    }
    while(i<=mid)
        arr[k++] = b[i++];
    while(j<=high)
        arr[k++] = b[j++];
}

int merge_sort(int *arr,int *b,int low,int high)
{
    int mid;
    if(low<high)
    {
        mid = (low)+(high - low)/2;
        merge_sort(arr,b,low,mid);
        merge_sort(arr,b,mid+1,high);
        merge(arr,b,low,mid,high);
    }
    return 0;
}

int temp_merge(int *arr,int *b,int low,int mid,int high)
{
    int i,j,k;
    i = low;
    j = mid+1;
    k = low;

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

int temp_merge_sort(int *arr,int *b,int low,int high)
{
    int mid;
    if(low<high)
    {
        mid = (low)+(high - low)/2;
        temp_merge_sort(arr,b,low,mid);
        temp_merge_sort(arr,b,mid+1,high);
        temp_merge(arr,b,low,mid,high);
    }
    return 0;
}

int main()
{
    int a[100],b[100],i;
    a[0] = 34;
    a[1] = 3;
    a[2] = 14;
    a[3] = 4;
    a[4] = 25;
    a[5] = 67;
    a[6] = 11;
    a[7] = 8;
    a[8] = 12;
    a[9] = 1;
    printf("contents of array a\n");
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    merge_sort(a,b,0,9);
    printf("after using merge_sort function\n");
    printf("contents of auxillary array b\n");
    for(i=0;i<10;i++)
        printf("%d ",b[i]);
    printf("\n");
    printf("contents of array a\n");
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    a[0] = 34;
    a[1] = 3;
    a[2] = 14;
    a[3] = 4;
    a[4] = 25;
    a[5] = 67;
    a[6] = 11;
    a[7] = 8;
    a[8] = 12;
    a[9] = 1;
    printf("contents of array a after reassigning values\n");
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    temp_merge_sort(a,b,0,9);
    printf("after using temp_merge_sort function\n");
    printf("contents of auxillary array b\n");
    for(i=0;i<10;i++)
        printf("%d ",b[i]);
    printf("\n");
    printf("contents of array a\n");
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
}

我得到了这段代码的以下输出

contents of array a
34 3 14 4 25 67 11 8 12 1 
after using merge_sort function
contents of auxillary array b
3 4 14 25 34 1 8 11 12 67 
contents of array a
1 3 4 8 11 12 14 25 34 67 
contents of array a after reassigning values
34 3 14 4 25 67 11 8 12 1 
after using temp_merge_sort function
contents of auxillary array b
34 3 14 4 25 67 11 8 12 1 
contents of array a
34 3 14 4 25 67 11 8 12 1

最初我用一些数字填充数组。然后我调用函数 merge_sort。此函数递归调用自身，直到 low 小于 high。然后对子数组进行合并操作。这是在函数合并中实现的，其中将原始数组的第一个元素复制到辅助数组，然后执行合并操作。这工作正常，生成的排序数字将存储在原始数组中。

之后我用未排序的值重新填充原始数组并调用函数 temp_merge_sort 函数。这类似于 merge_sort 函数，只是在此合并操作是由 temp_merge 函数执行的。在这个函数中，我没有将原始数组值从低到高复制到辅助数组，而是直接对原始数组的内容进行合并操作，并将结果复制到辅助数组。这不能正常工作，辅助数组的内容与未排序的原始数组保持不变。我不明白我在哪里犯了错误。有人可以帮忙吗？？？

-谢谢

Answer 1

在每次通过时，您都将“已排序”元素放入 b 中；但是由于您的代码假设 arr 中的元素变得越来越有序，您正在执行的操作没有做任何有用的事情(因为您需要从 中复制已排序的元素b 返回到 arr，或者依赖日益排序的 b 作为进一步排序的数据源)。

鉴于您当前的代码，我无法想到“一行”解决方案 - 但这本质上就是您遇到的问题。