4

我正在尝试使用 LISP 进行快速排序，但我的函数输出有问题。

(defun qsort (L)
   (cond
   ((null L) nil)
   (t(append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or(null a)(null b) nil))
    (( < a (car b)) (list< a (cdr b)))
    (t(cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or( null a)(null b) nil))
    (( >= a (car b)) (list> a (cdr b)))
    (t(cons (car b) (list> a (cdr b))))))

我的问题是当list<和list>=完成时，列表总是以 .T 结尾。例如：

> (list< '4 '(1 5 3 8 2))
Entering: LIST<, Argument list: (4 (1 5 3 8 2))
 Entering: LIST<, Argument list: (4 (5 3 8 2))
  Entering: LIST<, Argument list: (4 (3 8 2))
   Entering: LIST<, Argument list: (4 (8 2))
    Entering: LIST<, Argument list: (4 (2))
     Entering: LIST<, Argument list: (4 NIL)
     Exiting: LIST<, Value: T
    Exiting: LIST<, Value: (2 . T)
   Exiting: LIST<, Value: (2 . T)
  Exiting: LIST<, Value: (3 2 . T)
 Exiting: LIST<, Value: (3 2 . T)
Exiting: LIST<, Value: (1 3 2 . T)
(1 3 2 . T)

为什么(4 NIL)评估为 T？

4

6 回答 6

8

你的问题list<和问题list>=在于((or ( null a)(null b) nil))，它应该是(( or( null a)(null b)) nil)。注意nil被移到条件之外作为返回值。

此外，根据你的定义，list>=你在打电话list>，但我很肯定你的意思是list>=。

我还建议一些缩进来解决 lisp 的易读性，如下所示

(defun qsort (L)
  (cond
    ((null L) nil)
    (t
      (append
        (qsort (list< (car L) (cdr L)))
        (cons (car L) nil) 
        (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((< a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((>= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))

一些测试如下：

(list< '4 '(1 5 3 8 2))
=> (1 3 2)

(list>= '4 '(1 5 3 8 2))
=> (5 8)

(qsort '(1 5 3 8 2))
=> (1 2 3 5 8)
于 2013-09-29T19:34:41.133 回答
1

Lisp 有不同种类的集合。我认为使用快速排序对列表进行排序不是一个好的选择。在C++中STL的实现中，list的排序方式是merge-sort。我尝试使用数组的集合实现 3 路快速排序。

(defun quick-sort (arr start end)
  "Quick sort body"
  (if (< start end)
  (let ((n-pair (partition arr start end)))
  (quick-sort arr start (car n-pair))
  (quick-sort arr (cdr n-pair) end))
))

(defun partition (arr start end)
 "Partition according to pivot."
 (let ((pivot (aref arr start)) (cur start))
 (loop while (<= start end) do
  (cond
    ((< pivot (aref arr start)) ; pivot < arr[start], swap with arr[end]
     (swap arr start end) (decf end))
    ((> pivot (aref arr start)) ; pivot > arr[start], swap with arr[start]
     (swap arr cur start) (incf cur) (incf start))
    (t                          ; otherwise
     (incf start))))
    (cons (decf cur) start)))

(defun swap (arr i j)
 "Swap element of arr"
 (let ((tmp (aref arr i)))
 (setf (aref arr i) (aref arr j))
 (setf (aref arr j) tmp)))
于 2014-01-03T04:56:58.643 回答
1

我建议像这样更改 liya babu/Will Ness 的代码：

(defun quick (list)
  (if (null list) nil
      (let ((pivot (first list)) (less nil) (greater nil))
        (dolist (i (rest list))
          (if (< i pivot) (push i less) (push i greater)))
        (append (quick less) (list pivot) (quick greater)))))

虽然只是稍微编辑了一下，但我发现它更加简洁和简洁。

于 2019-01-13T13:05:21.143 回答
1 
(defun quick (list)
  (when (< = (length list) 1) (return-from quick list))
  (let ((pivot (car list)) (rest (cdr list)) (less nil) (greater nil))
    (loop for i in rest do
      (if (< i pivot) (push i less) (push i greater)))
    (append (quick less) (list pivot) (quick greater))))
于 2015-11-12T15:02:26.627 回答
0

程序中有一些错误。更正后的程序是：

(defun qsort (L)
   (cond
   ((null L) nil)
   (t (append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or (null a) (null b)) nil)
    (( < a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or ( null a)(null b)) nil)
    (( >= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))
于 2014-10-08T09:46:39.847 回答
-1

这也应该有效：

(defun qsort (l)
  (cond
   ((null l) nil)
   (t (append
       (qsort (car(list<> (car l)(cdr l))))
       (cons (car l) nil)
       (qsort (cadr(list<> (car l)(cdr l))))))))

(defun list<> (a b &optional rl rr)
    (cond
     ((null b) (list rl rr))
     ((<=(car b)a) (list<> a (cdr b) (cons (car b) rl) rr))
     (t (list<> a (cdr b)rl (cons (car b) rr)))))

(setq l (loop for j from 1 to 20 append (list(random 100))))
(qsort l)
;=> (86 99 9 31 66 58 57 43 48 21 51 0 32 69 39 47 59 76 69 23)
;=> (0 9 21 23 31 32 39 43 47 48 51 57 58 59 66 69 69 76 86 99)
于 2017-09-19T14:32:52.630 回答