sorting - 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))

(Demo)

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