6．程序设计举例

　　（1）快速排序
　　排序是经常遇到的一种操作，它有很多不同的算法，下面我们通过快速排序的例子，来说明如何用LISP编写排序程序。
　　快速排序的思想是这样的：首先以表的第一个元素x为基准，将表中比x大的元素放入一个表中，把比x小的元素放入另一个表中，然后将这两个表分别进行排序，并将排序结果同x一起进行合并，作为总的排序结果回送。

　　为了定义快速排序程序QUICK-SORT函数，首先定义两个辅助函数LARGE和SMALL。其中LARGE的功能是得到表L中比L的第一个元素大的所有元素，而SMALL则是得到L中小于等于L的第一个元素的所有元素（但不包括L的第一个元素）。为了叙述的方便，前者记做large，后者记做small，而L的第一个元素记做first。QUICK-SORT通过递归的方式定义，其思想是（假定按从大到小的方式排序）：如果large的排序结果是large－sort，small的排序结果是small－sort，则对L的排序结果是将large－sort、first和small－sourt按顺序合并在一起。其中的"将large－sort、first和small－sourt按顺序合并在一起"体现了按从大到小顺序排列，如果改为"将small－sort、first和large－sort按顺序合并在一起"则是按从小到大顺序排列。

（DEFUN QUICK-SORT）（L）
（COND（（NULL L）NIL）
（T（APPEND（QUICK-SORT（LARGE L））
（LIST （CAR L））
（QUICK-SORT（SMALL L））））））
（DEFUN LARGE（L）
（MAPCAN '（LAMBDA（x）
（COND（（＞ x（CAR L））（LIST x））
（T NIL）））
（CDR L）））
（DEFUN SMALL（L）
（MAPCAN '（LAMBDA（x）
（COND（（＜＝x（CAR L））（LIST x））
（T NIL）））
（CDR L）））
　　函数QUICK－SORT是进行快速排序的主函数，LARGE用来求出L中比L的第一个元素大的所有元素，SMALL用来求出L中小于等于L的第一个元素的所有元素。
　　其中，MAPCAN函数是一个系统函数，其功能基本同MAPCAR，只是在完成MAPCAR之后，MAPCAN对MAPCAR的回送值s进行一些处理，其处理方法是：若s的某个元素是表，则该表的元素是MAPCAN的回送表中的元素，若s的某个元素是NIL或原子，则该元素不在MAPCAN的回送表中出现。
试比较以下两个结果：
（MAPCAR 'CAR '（（（a）b）（x y）（NIL z）（（1 2）3）））
==>（（a）x NIL（1 2））
（MAPCAN 'CAR '（（（a）b）（x y）（NIL z）（（1 2）3）））
==>（a 1 2）