全部版块 我的主页
论坛 数据科学与人工智能 数据分析与数据科学 R语言论坛
2794 4
2015-04-04
小弟在学习 r语言编程艺术的时候,
遇到一个递归的问题。在书中p148页
程序是用来排序的,很简单。

qs<-function(x){

        if(length(x)<=1) return(x)

        pivot<-x[1]

        therest<-x[-1]

        sv1<-therest[therest<piot]

        sv2<-therest[therest>=piot]

        sv1<-qs(sv1)

        sv2<-qs(sv2)

        return(c(sv1,pivot,sv2))

}


里面递归了qs函数。

我有一点看不明白。 r 语言应该是每递归一次,就出一个return(c(sv1,pivot,sv2)) 吧。不然的,

就得不到最后的结果了。因为每一次递归应该会出现pivot.



二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2015-4-4 10:29:34
这是一个实现快速排序的程序,只要了解了快速排序的算法,理解起来应该没有问题
http://zh.wikipedia.org/wiki/快速排序
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2015-4-4 10:32:48
毓闻 发表于 2015-4-4 10:29
这是一个实现快速排序的程序,只要了解了快速排序的算法,理解起来应该没有问题
http://zh.wikipedia.org/ ...
我的意思,递归的思路应该是 每递归一次,都应该 return一下结果吧。
如果时递归完,再给出最后的结果就不对了
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2015-4-4 12:37:08
jackylee2010 发表于 2015-4-4 10:32
我的意思,递归的思路应该是 每递归一次,都应该 return一下结果吧。
如果时递归完,再给出最后的结果就 ...
举个简单例子,对 (4, 2, 5, 1, 3) 排序。
第1次调用qs()函数时,pivot = 4, SV1 = (2, 1, 3), SV2 = (5).
     这时对SV1 = (2, 1, 3)调用qs()函数,pivot' = 2, SV1' = (1), SV2' = (3).
            再对SV1' = (1)调用qs()函数,因为长度为1,直接返回原值;
            同样的对SV2' = (3)调用qs()函数也返回原值。
     所以SV1 = qs(SV1)得到的结果就是SV1 = (SV1', pivot', SV2') = (1, 2, 3);
     SV2 = qs(SV2)很容易看出结果是SV2 = (5).
回到第1层调用,返回结果(SV1, pivot, SV2) = (1, 2, 3, 4, 5),得到正确排序。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2015-4-4 16:46:33
get it.
3Q.
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群