作者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