2016-10-22 92 views
4

從書羅伯特·塞奇威克&凱文·韋恩算法第四版歸併排序基本情況(遞歸)解剖

在遞歸部分基本情況代碼

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

你有你的條件,比如'如果(完=開始)'?而不是'if(end == start)'? –

+0

@MuhammadAhmad,thanx mate!是的,如果我寫'(結束==開始)' – michel

回答

3

這是正確的,因爲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,但你不這樣做。也許你真的希望它是:空分(.....)

+0

感謝您讓我知道我用void做的錯誤。 – michel

+0

你能解釋一下在這段代碼中它是如何來無限循環的嗎? (a,5,3);其中,(a,b,b,b,c)分別代表(a,b,c)。 }' – michel

+0

@Michel如果使用==而不是'<=',調用'divide(a,5,3)'會導致無限循環,因爲:第一次'mid'變爲4(即(5 3)/ 2)。然後函數使用'divide(a,5,4)'調用它自己。這個時間'mid'變爲4(即(5 + 4)/ 2)。然後函數使用'divide(a,5,4)'調用它自己。再次同樣的電話!所以這將永遠持續下去。 – 4386427

1

可以編寫功能區劃的遞歸部分如下

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

我認爲它與@ 4386427的答案几乎相同,除了返回類型是'void'或將'end> start'更改爲'start

+0

如果您認爲返回類型應該是'void'而不是發佈一個新的答案,並且代碼中包含完全相同的代碼,那麼您應該對答案留言。 –

+0

嗯你是對的!基本上和我一樣遵循Thomas H. Cormen的Introduction to Algorithms的僞代碼 – Shateel