Apr
10
在王老师办公室上网玩的时候无意间看到了这个：
用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)))))))