归并排序基本情况（递归）解剖

Question

从书罗伯特·塞奇威克&凯文·韦恩算法第四版

在递归部分基本情况代码

if(end <= start) 
    { 
     return; 
    } 

但我检查end永不低于start索引。只剩下1个元素时发生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发生在divide(a,2,2)函数调用。

现在中旬是第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)。

也许这是要捕捉如果从另一个调用除法功能一段代码以不正确的方式，例如，

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

在任何情况下，它可能并不重要性能 - 一个优化的编译器无论如何都会重新安排你的事情。

顺便说一句：请注意，你的函数据说返回一个int，但你不这样做。也许你真的希望它是：空分（.....）

Answer 2

可以编写功能区划的递归部分如下

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