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

chenge · April 08, 2014 · Last by absente replied at September 19, 2018 · 6444 hits

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

Reply to 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/

Reply to absente

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

Reply to chenge

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

Reply to absente

APL 门槛比较高啊。

Reply to chenge

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

Reply to absente

kx 的快排链接有么?

Reply to absente

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

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

Reply to chenge

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

chenge in 来,一起复习一下排序算法 mention this topic. 13 Jan 19:16
You need to Sign in before reply, if you don't have an account, please Sign up first.