在C语言中使用递归合并排序 [英] merge sort using recursion in c languaage

问题描述

#include<stdio.h>
#include<conio.h>
int arr[20];       
void main()
{
    int n,i;
    clrscr();
    printf("\n\t\t\t------Merge Sorting------\n\n");
    printf("Enter the size of array\n");
    scanf("%d",&n);
    printf("Enter the elements:\n");
    for(i=0; i < n; i++)
    {
        scanf("%d",&arr[i]);
    }
    merge_sort(arr,0,n-1);
    printf("\n\n\t\t\t-----Merge Sorted Elements-----\n\n");
    printf("Sorted array:\t");
    for(i=0; i < n; i++)
    {
        printf("\t%d",arr[i]);
    }
    getch();
}

int merge_sort(int arr[],int low,int high)
{
    int mid;
    if(low < high)
    {
        mid=(low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);
        merge(arr,low,mid,high);
    }
}
int merge(int arr[],int l,int m,int h)
{
    int arr1[10],arr2[10];
    int n1,n2,i,j,k;
    n1=m-l+1;
    n2=h-m;
    for(i=0; i <  n1; i++)
    {
        arr1[i]=arr[l+i];
    }
    for(j=0; j < n2; j++)
    {
        arr2[j]=arr[m+j+1];
    }
    arr1[i]=9999;
    arr2[j]=9999;
    i=0;
    j=0;
    for(k=l; k <=h; k++)
    {
        if(arr1[i]<=arr2[j])
            arr[k]=arr1[i++];
        else
            arr[k]=arr2[j++];
    }
}

如果在此程序中我要输入大小为7的数组，则在检查条件是否为(0 <6)之后，将main()的merge_sort(arr，0,6)传递给相应的函数，然后在中间变为3，则存在一个低= 0且mid = 3的递归调用，然后这次mid为1再次具有(arr，0,1)..的递归调用，依此类推，直到low和mid等于0，则存在条件失败，因为if(0< 0)不为真

if in this program i am taking input an array of size 7.so from main() merge_sort(arr,0,6) is passed to the respective function after that condition is checked if(0<6) then there mid becomes 3 ,then there is a recursive call with low = 0 and mid = 3,then this time mid is 1 again recursive call with(arr,0,1) ..and so on till low and mid equals 0 ,then there if condition fails because if(0<0) is not true

但是我能够理解merge_sort(arr，mid + 1，high);被调用?但是该程序运行良好.请解释编译器如何调用merge_sort(arr，mid + 1，high)

but and i am able to understand how merge_sort(arr,mid+1,high); is being called?but this program runs fine .please explain how the compiler is calling merge_sort(arr,mid+1,high)

推荐答案

基于注释，真正的问题是:给定以下递归代码:

Based on comments, the real question is: given this bit of recursive code:

int merge_sort(int arr[],int low,int high)
{
    int mid;
    if(low < high)
    {
        mid=(low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);   // THIS ONE
        merge(arr,low,mid,high);
    }
}

由于指示的行又递归到相同的功能，如何到达指示的行?

How can the indicated line ever be reached, since the line before it recurses into the same function?

在条件块中，mid的值首先设置为低点和高点之间的值.然后，此mid变为下一次迭代的high，使low和high靠得更近.最终if(low < high)将失败，从而终止递归操作.

Within the conditional block, the value of mid is first set to a value between the low and high points. This mid then becomes the high for the next iteration, bringing low and high closer together. Eventually if(low < high) will fail, terminating that leg of recursion.

这篇关于在C语言中使用递归合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！