Ruby 一个优雅的快排

towonzhou · 2013年08月24日 · 最后由 LiKour 回复于 2013年08月26日 · 2663 次阅读
def quick_sort list
    (x = list.pop) ? quick_sort(list.select {|i| i <= x}) + [x] + quick_sort(list.select {|i| i > x}) : []
end 

好吧,有点儿慢....

看不懂,求逐字解释...

#1 楼 @blacktulip x 是基准,把小于或等于 x 的放在 x 的左边,大于 x 的放在 x 右边.....

好吧... 看到递归我就头大 -_-

thanks

用 partition

#1 楼 @blacktulip

qs([]) ->
    [];
qs([H|T]) ->
    qs([E || E <- T, E <= H]) ++ [H] ++ qs([E || E <- T, E > H]).

#5 楼 @bhuztez 这是哪国的英文...

怎么不用 Enumerable#partition

#7 楼 @doitian 用了好像也短不了多少啊

#8 楼 @blacktulip 用了就是这样:

def qs x, *xs
  l, r = xs.partition {|e| e <= x }
  x ? [*qs(l), x, *qs(r)] : []
end

#9 楼 @luikore thx,其实就是把两个 select 换成 partition 了

select 给你解决了大部分问题

#11 楼 @LiKour 恩,如果不提供 select 的话,自己实现一个就是..

#12 楼 @towonzhou mergesort 也可以用你这个方法哦,partition => merger

需要 登录 后方可回复, 如果你还没有账号请 注册新账号