在王老师办公室上网玩的时候无意间看到了这个:

用Haskell实现的快速排序:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

好简洁。

[]代表空list,所以第一行的意思就是,如果输入是空列表,输出也是空列表。

x:xs的意思是,一个list,第一个元素是x,剩下的是xs。(我不懂Haskell,我猜这就是lisp里的car/cdr吧)。

++的意思是把各个列表连结成一个大列表。

filter(<x) xs 是从xs中挑出所有小于x的元素组成列表。filter(>=x) xs 同理。

所以,上面这个快速排序实现的第二行的意思就是:组成一个列表,其中,所有小于x的排左边,并且进行快速排序;所有大于等于x的排右边,并且快速排序;x排中间。

另外,附上John Hughes写的为神马函数式编程很重要,晚上读一读。

补充:写了个scheme的实现:

(define (quicksort x)
  (cond
   ((null? x) ‘())
   (else (append
   (quicksort (filter (lambda (y) (< y (car x))) (cdr x)))
   (list (car x))
   (quicksort (filter (lambda (y) (>= y (car x))) (cdr x)))))))

, ,
Trackback

2 comments untill now

  1. Haskell真简洁啊~递归程序写的真漂亮

  2. parachute @ 2012-09-26 14:52

    这个的时间复杂度怎样?C里面调用库里面的快排也就一行再写一个一行的函数。

Add your comment now