10.4 示例：快速排序法(Example: Quicksort)

图 10.1 包含了重度依赖宏的一个示例函数 ── 一个使用快速排序演算法 λ 来排序向量的函数。这个函数的工作方式如下:

(defun quicksort (vec l r)
  (let ((i l)
        (j r)
        (p (svref vec (round (+ l r) 2))))    ; 1
    (while (<= i j)                           ; 2
      (while (< (svref vec i) p) (incf i))
      (while (> (svref vec j) p) (decf j))
      (when (<= i j)
        (rotatef (svref vec i) (svref vec j))
        (incf i)
        (decf j)))
    (if (>= (- j l) 1) (quicksort vec l j))    ; 3
    (if (>= (- r i) 1) (quicksort vec i r)))
  vec)

图 10.1 快速排序。

1. 开始你通过选择某个元素作为主键（ pivot ）。许多实现选择要被排序的序列中间元素。
2. 接着你分割（partition）向量，持续交换元素，直到所有主键左边的元素小于主键，右边的元素大于主键。
3. 最后，如果左右分割之一有两个或更多元素时，你递归地应用这个算法至向量的那些分割上。

每一次递归时，分割越变越小，直到向量完整排序为止。

在图 10.1 的实现里，接受一个向量以及标记欲排序范围的两个整数。这个范围当下的中间元素被选为主键 ( p )。接着从左右两端开始产生分割，并将左边太大或右边太小的元素交换过来。(将两个参数传给 rotatef 函数，交换它们的值。)最后，如果一个分割含有多个元素时，用同样的流程来排序它们。

除了我们前一节定义的 while 宏之外，图 10.1 也用了内置的 when , incf , decf 以及 rotatef 宏。使用这些宏使程序看起来更加简洁与清晰。