C语言 归并排序基本情况(递归)分解

Question

选自《Robert Sedgewick &凯文·韦恩算法第四版

在递归部分中，基准代码为

if(end <= start)
    {
        return;
    }

但是我检查了end永远不会低于start指数。只有当只剩下一个元素时才会发生end = start。那么为什么只有一个条件等于=的情况下使用<=小于运算符呢?

假设取一个数组a[8,5,3]。

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

之后

a[8,5] and a[3]

divide(a,0,1) and divide(a,2,2), merge(a,0,1,2)divide(a,0,1)中的start小于end, start=end发生在divide(a,2,2)函数调用中。

现在mid是第0个索引

a[8] and a[5] 

divide(a,0,0) and divide(a,1,1), merge(a,0,0,1)在这两个函数中，start=end只为真。

所以字面上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:注意，你的函数说返回int，但你没有这样做。也许你真的希望它是:voiddivide(.....)

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