合并排序基本案例（递归）剖析

Question

摘自 Robert Sedgewick 和 Kevin Wayne 算法第 4 版

在递归部分基本案例代码是

if(end <= start)
    {
        return;
    }

但我检查过 end 永远不会低于 start 指数。只有 end = start 只剩下 1 个元素时才会发生。那么为什么在只有一个等于 = 的条件始终有效的情况下使用 <= 小于运算符？

假设一个数组a[8,5,3]被采用。

现在中间点是第一个索引所以除法后

a[8,5] and a[3]

divide(a,0,1) and divide(a,2,2), merge(a,0,1,2) start is smaller than end in divide(a,0,1) and start=end happen in divide(a,2,2) function call.

现在 mid 是第 0 个索引。

a[8] and a[5]

divide(a,0,0) and divide(a,1,1), merge(a,0,0,1) here in both function call start=end is only true.

所以从字面上看 end 永远不会小于 start 因此 end<start 永远不会发生。只有 end=start 发生。

谁能解释一下为什么我们在合并排序的基本情况下使用 <（小于）运算符？

完整的递归代码

int divide(int a[], int start, int end)
{
    int mid;

    if(end<=start)
    {
        return;
    }
    else
    {
        mid = (start+end)/2;
        divide(a, start, mid);
        divide(a, mid+1, end);
        merge(a, start, mid, end);
    }
}

Answer 1

divide 函数从不使用参数调用自身是正确的，因此end < start。因此，if 语句也可以是 if (end == start).

如果从 另一段 代码中以不正确的方式调用 divide 函数，例如

void foo(int a[]) 
{ 
    divide(a, 5, 3);
}

如果您的检查只是 == 而不是 <=，那将导致无限循环。因此使用 <=.

似乎更安全

原来的代码也可以这样重写：

int divide(int a[], int start, int end)
{
    int mid;

    if(end > start)
    {
        mid = (start+end)/2;
        divide(a, start, mid);
        divide(a, mid+1, end);
        merge(a, start, mid, end);
    }
}

在任何情况下，这可能对性能无关紧要 - 优化编译器无论如何都会重新安排。

BTW: Notice that your function is said to return an int but you don't do that. Maybe you really want it to be: void divide(.....)

Answer 2

你可以像下面这样编写函数 divide 的递归部分

void divide(int a[], int start, int end)
{
    int mid;

    if(start < end)
    {
        mid = (start+end)/2;
        divide(a, start, mid);
        divide(a, mid+1, end);
        merge(a, start, mid, end);
    }
}

合并排序基本案例（递归）剖析

Merge Sort Base Case (Recursion) Dissect

c

mergesort