lisp 中的非破坏性排序？

Question

我的任务是创建一个程序，在其中我需要一个函数来 return 排序列表（按字母顺序）。但是，我无法使用和 "non-functional" 函数，例如 "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)

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

Answer 2

如果你的破坏性排序做一些事情，比如交换两个相邻的元素，这两个元素被你保持原样的元素包围，那么一个非破坏性的方法是创建一个新的列表，其中包含交换的这两个元素，被其他元素包围.然后使用该新列表作为后续排序操作的基础。

破坏性地，您的工作列表从头到尾都是一样的，您通过将一个 "place" 中的值替换为另一个 "place" 中的值来修改它。非破坏性地，在每一步创建一个成为工作列表的新列表。

我会把实现留给你。

lisp 中的非破坏性排序？

Non-destructive sort in lisp?

lisp

sorting