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

chenge · 2014年04月08日 · 最后由 absente 回复于 2018年09月19日 · 6171 次阅读

微博上知道了《啊哈,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/

还是喜欢这个写法:

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

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

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

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

坐等 @bhuztez 贴 erlang

zgm 回复

来贴个 APL:

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}
q:{f:*x@1?#x;:[0=#x;x;,/(_f x@&x<f;x@&x=f;_f x@&x>f)]}
q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]}

https://www.dyalog.com/blog/2014/12/quicksort-in-apl/ https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#K https://lifeisalist.wordpress.com/2014/11/21/quicksort-in-q/

absente 回复

能否解读一下呢?看不懂啊。

chenge 回复

有空再解读,这三个语句用到的很多词汇我也没用过

absente 回复

APL 门槛比较高啊。

chenge 回复

对,不过这三个里面,K 是最难懂的,APL 只是符号奇葩一点。Q 是相对比较容易懂的。基本上去 https://code.kx.com 仔细看看文档,就能懂

absente 回复

kx 的快排链接有么?

absente 回复

q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]}

可读性不好啊。有没有好理解的版本?

chenge 回复

没仔细找,回头我留意一下。(备注到 issue 里了

chenge 来,一起复习一下排序算法 提及了此话题。 01月13日 19:16
需要 登录 后方可回复, 如果你还没有账号请 注册新账号