理解mergesort的递归

Question

我看到的大多数mergesort实现与此类似.算法书介绍以及我搜索的在线实施.我的递归方法并没有比弄乱Fibonacci一代(这很简单),所以也许是多次递归让我大吃一惊,但是我甚至无法介绍代码并理解甚至在我击中之前发生了什么合并功能.

它如何踩过这个？我应该采取一些策略或阅读来更好地理解这里的过程吗？

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);
    }
}

和合并(虽然坦率地说,在我到达这一部分之前,我在精神上陷入困境)

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];
}

Answer 1

MERGE SORT:

1)将阵列分成两半
2)对左半部分进行
排序3)对右半部分进行排序
4)将两半合并在一起

Answer 2

我认为MergeSort中的"排序"函数名称有点用词不当,它应该被称为"除法".

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

每次函数递归时,它都会在输入数组的较小和较小的细分上工作,从它的左半部分开始.每次函数从递归返回时,它将继续运行并开始在右半部分工作,或者再次递增并处理更大的一半.

像这样

[************************]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

Answer 3

一个显而易见的事情是在一个小阵列上尝试这种合并排序,比如8号(2的功率在这里很方便),在纸上.假装你是一台执行代码的计算机,看看它是否开始变得更清晰了.

你的问题有点含糊不清,因为你没有解释你发现令人困惑的内容,但听起来你正试图在你头脑中展开递归调用.这可能是好事,也可能不是好事,但我认为这很容易导致你的头脑过多.而不是试图从头到尾跟踪代码,看看你是否能够抽象地理解这个概念.合并排序:

1. 将阵列拆分成两半
2. 对左半部分进行排序
3. 排序右半部分
4. 将两半合并在一起

(1)对你来说应该是相当明显和直观的.对于步骤(2),关键见解是这样,数组的左半部分是一个数组.假设您的合并排序有效,它应该能够对数组的左半部分进行排序.对？步骤(4)实际上是算法的一个非常直观的部分.一个例子应该使它变得微不足道:

at the start
left: [1, 3, 5], right: [2, 4, 6, 7], out: []

after step 1
left: [3, 5], right: [2, 4, 6, 7], out: [1]

after step 2
left: [3, 5], right: [4, 6, 7], out: [1, 2]

after step 3
left: [5], right: [4, 6, 7], out: [1, 2, 3]

after step 4
left: [5], right: [6, 7], out: [1, 2, 3, 4]

after step 5
left: [], right: [6, 7], out: [1, 2, 3, 4, 5]

after step 6
left: [], right: [7], out: [1, 2, 3, 4, 5, 6]

at the end
left: [], right: [], out: [1, 2, 3, 4, 5, 6, 7]

因此,假设你理解(1)和(4),另一种思考合并排序的方法就是这样.想象一下别人写的mergesort(),你确信它有效.然后你可以使用该实现mergesort()来编写:

sort(myArray)
{
    leftHalf = myArray.subArray(0, myArray.Length/2);
    rightHalf = myArray.subArray(myArray.Length/2 + 1, myArray.Length - 1);

    sortedLeftHalf = mergesort(leftHalf);
    sortedRightHalf = mergesort(rightHalf);

    sortedArray = merge(sortedLeftHalf, sortedRightHalf);
}

请注意,sort不使用递归.它只是说"将两半分开然后合并它们".如果您理解上面的合并示例,那么希望您直观地看到此sort函数似乎按照它所说的那样...排序.

现在,如果你仔细看一下...... sort()看起来非常像mergesort()!那是因为它是mergesort()(除了没有基本情况,因为它不是递归的!).

但这就是我喜欢考虑递归函数的方法 - 假设函数在调用它时起作用.将它视为一个黑盒子,可以满足您的需求.当你做出这个假设时,弄清楚如何填写那个黑盒子通常很容易.对于给定的输入,您可以将其分解为较小的输入以馈送到黑匣子吗？解决之后,唯一剩下的就是在函数开始时处理基本情况(这是你不需要进行任何递归调用的情况.例如,mergesort([])只返回一个空数组;它不会' t进行递归调用mergesort()).

最后,这有点抽象,但理解递归的一个好方法实际上是使用归纳法编写数学证明.用于通过归纳编写证明的相同策略用于编写递归函数:

数学证明:

• 显示基本案例的声明是正确的
• 假设输入小于某些输入是正确的 n
• 使用该假设表明对于大小的输入仍然是正确的 n

递归函数:

• 处理基本案例
• 假设您的递归函数适用于小于某些输入的输入 n
• 使用该假设来处理大小的输入 n

Answer 4

关于合并排序的递归部分,我发现这个页面非常有用.您可以按照正在执行的代码进行操作.它会向您显示首先执行的操作以及接下来的操作.

汤姆