时间戳

首页 > 解决方案 > CLisp - 在快速排序中对两个列表进行排序和组合

recursion - CLisp - 在快速排序中对两个列表进行排序和组合

问题描述

我正在尝试在 CLisp 中实现快速排序，到目前为止，我能够围绕枢轴对列表进行分区。但是，当我尝试对子列表进行组合和递归排序时，我会遇到堆栈溢出或错误let，而且我不确定出了什么问题。这是我的代码：

(defun pivot (n xs)
  (list (getLesser n xs) (getGreater n xs))
)

(defun getLesser (m l)
  (cond
    ((null l) nil)
    ((<= m (car l)) (getLesser m (cdr l)))
    (t (cons (car l) (getLesser m (cdr l)))))
)

(defun getGreater (m l)
  (cond
    ((null l) nil)
    ((> m (car l)) (getGreater m (cdr l)))
    (t (cons (car l) (getGreater m (cdr l)))))
)


(defun quicksort (xs)
  (cond
    ((null xs) nil)
    (t
      (let (partition (pivot (car xs) xs))
        (cond
          ((null (car partition)) (cons (quicksort (cdr partition)) nil))
          ((null (cdr partition)) (cons (quicksort (car partition)) nil))
          (t (append (quicksort (car partition)) (quicksort (cdr partition)))))))))

我的想法是有一个局部变量partition，它是 2 个列表的列表，其中car partition数字列表小于枢轴，而cdr partition数字列表大于枢轴。然后，在最终cond构造中，如果没有小于枢轴的数字，我将对第二个列表进行递归排序；如果没有大于枢轴的数字，我将对第一个列表进行排序；否则我会递归地对两者进行排序并按顺序附加它们。谁能帮我吗？

标签： recursionsyntaxcommon-lispletclisp

解决方案

编译该文件会给您有关错误语法的提示。

GNU CLISP 产生这些诊断：

$ clisp -q -c foo.lisp
;; Compiling file /tmp/foo.lisp ...
WARNING: in QUICKSORT in lines 20..28 : Illegal syntax in LET/LET*: (PIVOT (CAR XS) XS)
         Ignore the error and proceed
;; Deleted file /tmp/foo.fas
There were errors in the following functions:
 QUICKSORT
1 error, 1 warning

SBCL 产生类似的诊断：

$ sbcl --eval '(compile-file "foo.lisp")' --quit
This is SBCL 1.3.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
; compiling file "/tmp/foo.lisp" (written 08 MAY 2019 08:58:54 PM):
; compiling (DEFUN PIVOT ...)
; compiling (DEFUN GETLESSER ...)
; compiling (DEFUN GETGREATER ...)
; compiling (DEFUN QUICKSORT ...)
; file: /tmp/foo.lisp
; in: DEFUN QUICKSORT
;     (LET (PARTITION (PIVOT (CAR XS) XS))
;       (COND ((NULL (CAR PARTITION)) (CONS (QUICKSORT #) NIL))
;             ((NULL (CDR PARTITION)) (CONS (QUICKSORT #) NIL))
;             (T (APPEND (QUICKSORT #) (QUICKSORT #)))))
; 
; caught ERROR:
;   The LET binding spec (PIVOT (CAR XS) XS) is malformed.
; 
; compilation unit finished
;   caught 1 ERROR condition


; /tmp/foo.fasl written
; compilation finished in 0:00:00.021

然后您可以在CLHS中查找预期的语法：http ://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/speope_letcm_letst.html

推荐阅读