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

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。这个函数递归地调用自己，直到低，小于高。然后对子数组执行合并操作。这是在函数合并中实现的，其中原始数组的第一个元素被复制到辅助数组中，然后执行合并操作。这是很好的工作，得到的排序数字将存储在原始数组中。

之后，我将使用未排序的值填充原始数组，并调用函数temp_merge_sort函数。这与merge_sort函数类似，只是在此合并操作中由temp_merge函数执行。在此函数中，我直接对原始数组的内容执行合并操作，并将结果复制到辅助数组，而不是将原始数组值从低到高复制到辅助数组。这不是很好，辅助数组的内容与未排序的原始数组相同。我不明白我是怎么搞错的。有人能帮忙吗？

-Thank你

Answer 1

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

考虑到您当前的代码，没有“一行”解决方案，但这在本质上就是您的问题所在。