微博上知道了《啊哈，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 代码的可读性也很好。
历史
这个算法的发明者是一个科学家，曾经获得图灵奖
还是喜欢这个写法：
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
对
zgm
回复
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
#11
2018年09月18日
对
chenge
回复
chenge
回复
对，不过这三个里面，K 是最难懂的，APL 只是符号奇葩一点。Q 是相对比较容易懂的。基本上去 https://code.kx.com 仔细看看文档，就能懂
chenge
#14
2018年09月19日
对
absente
回复
absente
回复
q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]}
可读性不好啊。有没有好理解的版本？