LISP编程

Question

(defun bubbleUp (n)
  (cond
    ((null n) nil)
    ((null (cdr n)) n)
    ((> (car n) (car (cdr n)))
     (append (list (car (cdr n)))
             (bubbleUp (cons (car n) (cdr (cdr n))))))
    (t (append (list (car n)) (bubbleUp (cdr n))))))

我想编写一个使用此 bubbleUp 函数的排序函数。

对排序的调用将输出以下内容:

> (sort ‘(5 4 3 2 1)) > (1 2 3 4 5)

> (sort ‘(6 4 3 9 8))

> (3 4 6 8 9)

但我只想使用 LISP 函数:defun、cond、car、cdr、list、cons、append、>、<、>=、<=、= 和 null。我不想使用(setq 和 set)

Answer 1

据我了解你的问题你必须申请 bubble-up (这将是一种更容易命名函数的方式)再次直到 (apply #'< sorted-list)是真的，其中 sorted-list是 bubble-up 的结果.

当然，这只是一个家庭作业解决方案，如果性能可能成为问题，则不应使用。此外，您应该考虑在 SO 上完成作业是否聪明；-)

我想，最简单的模式应该是这样的(把你的函数 bubble-up 作为给定的):

(defun bubble-sort (list)
  (cond ((apply #'< list) list)
        (t (bubble-sort (bubble-up list)))))

CL-USER> (bubble-sort '(6 4 3 9 8 10 1 12))
==> (1 3 4 6 8 9 10 12)

但请注意，我不是一个非常有经验的 Lisp 程序员，这段代码非常低效。如果你真的想对列表进行排序，你应该使用 sort 并阅读更多关于尾调用优化和迭代的信息。信息选项卡包含更多资源。