2

该mergeSort算法是否使用相互递归？我意识到mergeSort调用merge函数并且它调用自身（mergeSort），但是由于merge不调用mergeSort它不是相互递归而只是递归吗？

function mergeSort(arr) {
    // split array
    ...
    return merge(mergSort(firstHalf), mergeSort(secondHalf));
}

function merge (array1, array2) {
    // merge both arrays
    ...
    return singleArray;
}
4

2 回答 2

2

正确：这是简单的递归。相互递归也称为间接递归：A调用B；B打电话给A。

您的分析完全正确：merge如果调用mergeSort，那么您将进行相互递归。在发布的代码中，调用merge是调用树上的简单父子链接。

于 2017-06-07T22:15:19.360 回答
1

接下来解释归并排序的相互递归，它是用于优化自顶向下归并排序以避免在合并过程中出现复制步骤的方法之一，其中合并的方向取决于递归的级别。另一种方法是传递一个标志作为合并方向的参数。在下面的示例代码中，a[] 是原始数组，b[] 是工作数组。TopDownSplitMergeAtoA 返回原始数组中的排序数据，TopDownSplitMergeAtoB 返回工作数组中的排序数据，TopDownSplitMergeAtoA 调用 TopDownSplitMergeAtoB，反之亦然（这是相互递归）。如果 TopDownSplitMergeAtoB 的子数组大小为 1，则唯一的复制操作会发生，在这种情况下，会将一个元素从原始数组复制到工作数组。

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee);

void MergeSort(int a[], size_t n)       // entry function
{
    if(n < 2)                           // if size < 2 return
        return;
    int *b = new int[n];
    TopDownSplitMergeAtoA(a, b, 0, n);
    delete[] b;
}

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
    if((ee - ll) == 1)                  // if size == 1 return
        return;
    size_t rr = (ll + ee)>>1;           // midpoint, start of right half
    TopDownSplitMergeAtoB(a, b, ll, rr);
    TopDownSplitMergeAtoB(a, b, rr, ee);
    Merge(b, a, ll, rr, ee);     // merge b to a
}

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
    if((ee - ll) == 1){                 // if size == 1 copy a to b
        b[ll] = a[ll];
        return;
    }
    size_t rr = (ll + ee)>>1;           // midpoint, start of right half
    TopDownSplitMergeAtoA(a, b, ll, rr);
    TopDownSplitMergeAtoA(a, b, rr, ee);
    Merge(a, b, ll, rr, ee);     // merge a to b
}

void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                      // b[]       index
    size_t l = ll;                      // a[] left  index
    size_t r = rr;                      // a[] right index
    while(1){                           // merge data
        if(a[l] <= a[r]){               // if a[l] <= a[r]
            b[o++] = a[l++];            //   copy a[l]
            if(l < rr)                  //   if not end of left run
                continue;               //     continue (back to while)
            while(r < ee)               //   else copy rest of right run
                b[o++] = a[r++];
            break;                      //     and return
        } else {                        // else a[l] > a[r]
            b[o++] = a[r++];            //   copy a[r]
            if(r < ee)                  //   if not end of right run
                continue;               //     continue (back to while)
            while(l < rr)               //   else copy rest of left run
                b[o++] = a[l++];
            break;                      //     and return
        }
    }
}
于 2017-06-08T20:01:23.543 回答