作者elba ( )
看板Prob_Solve
標題Re: [問題] 有關 MERGE SORT 的問題
時間Sat Feb 28 15:45:27 2009
※ 引述《s961639 (Nobodyknows)》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板]
: 作者: s961639 (Nobodyknows) 看板: C_and_CPP
: 標題: [問題] 有關 MERGE SORT 的問題
: 時間: Fri Feb 27 23:27:34 2009
: (非C相關問題 但找不到演算法相關版 故在求助個位板大)
: 這是MIT 出版 演算法概論中
: 合併排序的主程式 P32
: merge-sort (A,p,r)
: 1 if p < r
: 2 then q <- (p + r)/2
: 3 merge-sort (A,p,q)
: 4 merge-sort (A,q+1,r)
: 5 merge (A,p,q,r)
: 若今天index 為 1~8
: 小弟的問題在於
: 第一個merge-sort(line 3) 不斷的呼叫自己 直到 p=1 q=1
: 這樣 判斷式不成立 程式如何繼續執行?
若執行到第3行時p=1,q=1
進入函式merge-sort之後p=1,r=1
第1行的判斷式不成立,函式便會return,繼續執行第4行
: q<-(p+r)/2 之後
: 3 4 5 行是如何連續呼叫? 步驟大概是如何進行?
基本上就是不斷的把陣列分成前半部(第3行)與後半部(第4行)分別排序
再將排序好的陣列做合併(第5行)
因為不斷切半處理後會產生只有1個元素的陣列(當然是已排序)
合併的步驟就會開始執行
: 如果有大大 能告簡單說明
: 我真的事非常感激
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.164.102.239