The Two.

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

用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)))))))