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

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。然后对子数组执行合并操作。这是在函数merge中实现的，在该函数中，原始数组的第一个元素被复制到辅助数组，然后执行合并操作。这工作正常，得到的排序数字将存储在原始数组中。

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

-谢谢!

Answer 1

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

考虑到您当前的代码，我想不出“一行”解决方案——但这就是您的问题所在。