理解归并排序的递归 [英] Understanding the Recursion of mergesort

问题描述

我看到的大多数合并排序实现都与此类似.算法介绍书以及我搜索的在线实现.我的递归印章不会比弄乱斐波那契生成(这很简单)更进一步，所以也许是多次递归让我大吃一惊，但我什至无法单步执行代码，甚至在我击中之前就了解发生了什么合并功能.

Most of the mergesort implementations I see are similar to this. intro to algorithms book along with online implentations I search for. My recursion chops don't go much further than messing with Fibonacci generation (which was simple enough) so maybe it's the multiple recursions blowing my mind, but I can't even step through the code and understand whats going on even before I even hit the merge function.

它是如何逐步完成的?为了更好地理解这里的流程，我应该采取一些策略或阅读方法吗?

How is it stepping through this? Is there some strategy or reading I should undergo to better understand the process here?

void mergesort(int *a, int*b, int low, int high)
{
    int pivot;
    if(low<high)
    {
        pivot=(low+high)/2;
        mergesort(a,b,low,pivot);
        mergesort(a,b,pivot+1,high);
        merge(a,b,low,pivot,high);
    }
}

和合并(尽管坦率地说，我什至在进入这部分之前就被困在了精神上)

and the merge(although frankly I'm mentally stuck before I even get to this part)

void merge(int *a, int *b, int low, int pivot, int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=pivot+1;

    while((h<=pivot)&&(j<=high))
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    else
    {
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) a[k]=b[k];
}

推荐答案

我觉得 MergeSort 中的sort"函数名有点用词不当，应该叫divide".

I think the "sort" function name in MergeSort is a bit of a misnomer, it should really be called "divide".

这是正在进行的算法的可视化.

Here is a visualization of the algorithm in process.

每次函数递归时，它都会处理输入数组的越来越小的细分，从它的左半部分开始.每次函数从递归返回时，它都会继续运行，要么开始处理右半部分，要么再次向上递归处理更大的一半.

Each time the function recurses, it's working on a smaller and smaller subdivision of the input array, starting with the left half of it. Each time the function returns from recursion, it will continue on and either start working on the right half, or recurse up again and work on a larger half.

像这样

[************************]mergesort
[************]mergesort(lo,mid)
[******]mergesort(lo,mid)
[***]mergesort(lo,mid)
[**]mergesort(lo,mid)
 [**]mergesort(mid+1,hi)
[***]merge
   [***]mergesort(mid+1,hi)
   [**]mergesort*(lo,mid)
    [**]mergesort(mid+1,hi)
   [***]merge
[******]merge
      [******]mergesort(mid+1,hi)
      [***]mergesort(lo,mid)
      [**]mergesort(lo,mid)
       [**]mergesort(mid+1,hi)
      [***]merge
         [***]mergesort(mid+1,hi)
         [**]mergesort(lo,mid)
           [**]mergesort(mid+1,hi)
         [***]merge
      [******]merge
[************]merge
            [************]mergesort(mid+1,hi)
            [******]mergesort(lo,mid)
            [***]mergesort(lo,mid)
            [**]mergesort(lo,mid)
             [**]mergesort(mid+1,hi)
            [***]merge
               [***]mergesort(mid+1,hi)
               [**]mergesort(lo,mid)
                 [**]mergesort(mid+1,hi)
               [***]merge
            [******]merge
                  [******]mergesort(mid+1,hi)
                  [***]mergesort(lo,mid)
                  [**]mergesort*(lo,mid)
                    [**]mergesort(mid+1,hi)
                  [***]merge
                     [***]mergesort(mid+1,hi)    
                     [**]mergesort(lo,mid)
                      [**]mergesort(mid+1,hi)
                     [***]merge
                  [******]merge
            [************]merge
[************************]merge

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