lisp 中的非破坏性排序？

Question

我的任务是创建一个程序，在其中我需要一个函数来返回一个排序列表（按字母顺序）。但是，我无法使用“非功能性”功能，例如“set、setq”等……这包括内置的排序功能（因为它具有破坏性）。所以，我想知道是否有办法在 lisp 中构建非破坏性排序？

Answer 1

最简单的方法是在排序之前制作一个副本：

(sort (copy-seq input) predicate)

或者您自己编写一个排序函数，例如快速排序：

(defun qsort (input predicate)
  (if input
    (let* ((pivot (first input))
           (rest (rest input))
           (lesser (remove-if-not #'(lambda (x)
                                      (funcall predicate x pivot))
                                  rest))
           (greater (remove-if-not #'(lambda (x)
                                       (not (funcall predicate x pivot)))
                                   rest)))
      (append (qsort lesser predicate)
              (list pivot)
              (qsort greater predicate)))
    nil))

（演示）

请注意，可以对此进行优化以检测列表的已排序剩余部分，从而在未排序和已排序列表之间实现结构共享。