Ruby 一个优雅的快排

towonzhou · August 24, 2013 · Last by LiKour replied at August 26, 2013 · 2660 hits
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

You need to Sign in before reply, if you don't have an account, please Sign up first.