我尝试在Common Lisp中实现快速排序,以下是我的成果:
(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list))
(remove-if-not (lambda (n) (= n pivot)) list)
(quick-sort (remove-if-not (lambda (n) (> n pivot)) list))))
list))
显然,它可以工作,但我认为这段代码中有太多的重复。基本上,我们有三次:
(remove-if-not (lambda (n) (< n pivot)) list)
唯一区别这三个调用的方法是使用
>
、=
或者 <
。因此我的问题是:如何消除冗余并使代码更易读、更紧凑?
当然我可以将一些东西提取到一个函数中,例如:
(defun which (operator pivot list )
(remove-if-not (lambda (n) (funcall operator n pivot)) list))
(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(append (quick-sort (which #'< pivot list))
(which #'= pivot list)
(quick-sort (which #'> pivot list))))
list))
但我并不确定这是否是最佳方法。反复交换 pivot
和 list
仍然感觉有些笨拙。
我还想使用 flet
,它使函数的实际体更易读,但只是将复杂性转移到其他地方:
(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(flet ((left () (remove-if-not (lambda (n) (< n pivot)) list))
(middle () (remove-if-not (lambda (n) (= n pivot)) list))
(right () (remove-if-not (lambda (n) (> n pivot)) list)))
(append (quick-sort (left))
(middle)
(quick-sort (right)))))
list))
有其他的方法吗?