c - 合并排序基本案例(递归)剖析

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(.....)