快速排序是一种常见的排序手段，由C.A.R.Hoare在1960年提出。其基本思路为：
-
设定一个分界值，通常为第一个元素；
-
遍历列表，将所有小于分界值的元素集中到列表的左侧，所有大于或等于分界值的元素集中到右侧；
-
分别对左侧和右侧的元素进行快排；
-
重复上述的步骤，排序完成；
在平均状况下，排序n个元素需要$O(nlog n)$复杂度，最坏情况下需要$O(n^2)$,但一般很少出现这种情况。
从算法的原理可以看出，需要多次执行重复的操作，自然采用递归可以减少很多代码，若问递归技术哪家强？首屈一指Lisp,下面给出CL版本的快排实现（简易版本，只支持数字类型的列表，其他类型的排序只需增加一个比较函数即可，本文不扩展）：
(defun quickSort (lst)
(let
(
(len (list-length lst))
(st (lambda (l pk) ;; st函数实现上述第2步
(let ((left nil) (right nil))
(dolist (each l) (if (< each pk) (push each left) (push each right)))
(values left right)
)
)
)
)
(if
(< len 2)
lst
(multiple-value-bind (l r) (st (cdr lst) (car lst)) (append (quickSort l) (cons (car lst) (quickSort r))))
)
)
)
(quickSort '(1 2 6 3 5 4)) => (1 2 3 4 5 6)
st函数可以用宏来实现：
(defmacro st (lst pk)
(let ((gslist (gensym)))
`(let ((,gslist ,lst))
(let ((left nil) (right nil))
(dolist (each ,gslist) (if (< each ,pk) (push each left) (push each right)))
(values left right)
)
)
)
)
(defun quickSort (lst)
(let
(
(len (list-length lst))
)
(if
(< len 2)
lst
(multiple-value-bind (l r) (st (cdr lst) (car lst)) (append (quickSort l) (cons (car lst) (quickSort r))))
)
)
)
