Ruby 一个优雅的快排

towonzhou · 2013年08月24日 · 最后由 LiKour 回复于 2013年08月26日 · 2662 次阅读

def quick_sort list
    (x = list.pop) ? quick_sort(list.select {|i| i <= x}) + [x] + quick_sort(list.select {|i| i > x}) : []
end

好吧，有点儿慢....

blacktulip #1 2013年08月24日

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

towonzhou #2 2013年08月24日

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

blacktulip #3 2013年08月24日

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

thanks

jjym #4 2013年08月24日

用 partition

bhuztez #5 2013年08月24日

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

blacktulip #6 2013年08月24日

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

doitian #7 2013年08月24日

怎么不用 Enumerable#partition

blacktulip #8 2013年08月24日

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

luikore #9 2013年08月24日

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

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

blacktulip #10 2013年08月24日

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

LiKour #11 2013年08月24日

select 给你解决了大部分问题

towonzhou #12 2013年08月25日

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

LiKour #13 2013年08月26日

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

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