算法 啊哈,最美的快排算法

chenge · 发布于 2014年04月08日 · 最后由 bhuztez 回复于 2014年04月09日 · 3018 次阅读
4215

微博上知道了《啊哈,C》这本书,听说作者即将出版《啊哈,算法》。我也来凑个热闹。 邀请各位高手,通俗地介绍您的最美算法。

主题

先看代码吧,本来可以写成一行,我觉得换行写可读性好些。

def qs a
  (pivot = a.pop) ? 
    qs(a.select{|i| i <= pivot}) + [pivot] + qs(a.select{|i| i > pivot}) :
    []
end

#test
x = (1..10).to_a.shuffle
p x
p qs x

通俗地说,快排的故事是这样的:

话说一组胖子,长官要求按照体重排序,且看他如何做。第一位名叫张跑,貌似张飞,长官一声令下张跑出列,张跑差不多220斤。接下来长官要求张跑居中,比他轻的站左边,重的站右边。只见大部分都站到了左边,右边的不多几个。

代码中的pivot就是张跑。

接下来就是左右两组,重复这个过程,计算机术语叫递归。

为何最美

快排算法好在快,也容易理解。Ruby代码的可读性也很好。

历史

这个算法的发明者是一个科学家,曾经获得图灵奖

感受图形演示:http://ljs.io/projects/rainbow/

共收到 6 条回复
1232

还是喜欢这个写法:

def quick_sort2(arr)
  return [] if arr == []
  x, *xs = *arr
  left, right = xs.partition { |n| n < x }
  quick_sort2(left) + [x] + quick_sort2(right)
end
6291

@chenge 如果把 qs a i pivot 替换一下名称会不会更清晰

4215

#2楼 @swordray 你提供下方案吧。

6291

#3楼 @chenge 我的意思是 a 改名 array 这样会不会好看一点

115

坐等 @bhuztez 贴 erlang

96

#5楼 @zgm 要贴自己贴

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