Common lisp中的插入排序

Question

我想用这个 INSERT 函数在 common-lisp 中实现排序功能 k 表示带有数字和 val 的 cons 单元格，li 表示我要将 k 插入其中的列表。使用此功能，我可以列出单元格

(defun INSERT (li k)  (IF (eq li nil) (cons (cons(car k)(cdr k)) nil)
    (IF  (eq (cdr li) nil)
          (IF (< (car k)(caar li))  (cons (cons(car k)(cdr k)) li)
            (cons (car li)  (cons (cons(car k)(cdr k)) (cdr li)) )
          )
        (cond 
            (    (eq (< (caar li) (car k)) (< (car k) (caadr li)) ) 
               (cons  (car k)  (cons (cons (car k) (cdr k))  (cdr li))  )   )
            (t (cons (car li) (INSERT (cdr li) k))  )))))

而我想要的是下面这个函数的代码。它只有一个参数 li(non sorted list)

(defun Sort_List (li)(...this part...))

不使用赋值，使用 INSERT 函数

Answer 1

你的insert函数很奇怪。事实上，我发现它很难阅读，以至于我不知道它在做什么，除了不需要检查列表是否为空和其 cdr 是否为空。它还包含很多它不需要的东西，除非问题规范的某些部分要求您复制您正在插入的内容。

这是它的一个版本，它更容易阅读，并且在不需要时不会复制。请注意，这会将其参数与您的顺序相反：

(defun insert (thing into)
  (cond ((null into)
         (list thing))
        ((< (car thing) (car (first into)))
         (cons thing into))
        (t (cons (first into)
                 (insert thing (rest into))))))

现在，插入排序的算法是什么？嗯，本质上是：

遍历要排序的列表：
- 对于每个元素，将其插入到排序列表中；
- 最后 return 排序列表。

并且我们不允许使用赋值来执行此操作。

好吧，有一个标准技巧可以做这类事情，即使用带有 accumulator 参数的尾递归函数，它会累积结果。我们可以把这个函数写成一个显式的辅助函数，也可以让它成为一个本地函数。我打算做后者，因为没有理由让一个只在本地使用过的函数在全球范围内可见，而且因为（我假设这是家庭作业）它使得直接提交变得更加困难。

所以这里是函数的这个版本：

(defun insertion-sort (l)
  (labels ((is-loop (tail sorted)
             (if (null tail)
                 sorted
               (is-loop (rest tail) (insert (first tail) sorted)))))
    (is-loop l '())))

这种方法在 Scheme 中很自然，但在 CL 中不是很自然。另一种不使用赋值的替代方法，至少是明确地，是使用 do。这是一个使用 do:

的版本

(defun insertion-sort (l)
  (do ((tail l (rest tail))
       (sorted '() (insert (first tail) sorted)))
       ((null tail) sorted)))

关于这个版本有两个注意事项。

首先，虽然它不是明确地使用赋值，但很明显隐含地这样做。我认为这可能是作弊。
其次，它起作用的原因有点微妙：(insert (first tail) sorted) 中 tail 的值到底是什么，为什么？

一个更清晰的版本，但使用了您可能不知道的 loop，是

(defun insertion-sort (l)
  (loop for e in l
        for sorted = (insert e '()) then (insert e sorted)
        finally (return sorted)))

然而，这也非常明确地使用了赋值。

正如 Kaz 在下面指出的那样，有一种明显的方法（我应该已经看到了！）使用 CL reduce 函数来执行此操作。从概念上讲，reduce 的作用是通过调用一个带有两个参数的函数来连续折叠元素序列。所以，例如

(reduce #'+ '(1 2 3 4))

与

相同

(+ (+ (+ 1 2) 3) 4)

如果您使用 cons 作为函数，这将更容易看到：

>  > (reduce #'cons '(1 2 3 4))
(((1 . 2) . 3) . 4)

> (cons (cons (cons 1 2) 3) 4)
(((1 . 2) . 3) . 4)

当然，如上所述，insert 非常适合此操作：它获取一个有序列表并向其中插入一个新的对，return创建一个新的有序列表。有两个问题：

my insert 以错误的顺序接受参数（这可能就是为什么原来的以另一个顺序接受参数的原因！）；
需要有一种方法 'seeding' 初始排序列表，它将是 ()。

好吧，我们可以通过重写 insert 或将其包装在交换参数的函数中来修复错误的参数顺序：我会做后者，因为我不想重温我上面写的，我不想要两个版本的函数。

您可以 'seed' 通过将初始空值添加到要排序的列表之前，或者实际上 reduce 有一个特殊的选项来提供初始值，所以我们'我会用的。

所以使用 reduce 我们得到这个版本的 insertion-sort:

(defun insertion-sort (l)
  (reduce (lambda (a e)
            (insert e a))
          l :initial-value '()))

我们可以测试这个：

>  (insertion-sort '((1 . a) (-100 . 2) (64.2 . "x") (-2 . y)))
((-100 . 2) (-2 . y) (1 . a) (64.2 . "x"))

而且效果很好。

所以最后一个问题是：我们是否再次通过使用某些定义显然必须涉及赋值的函数来作弊？好吧，不，我们不是，因为您可以很容易地编写一个简化的 reduce 并发现它不需要使用赋值。这个版本比 CL 的 reduce 简单得多，特别是它明确需要初始值参数：

(defun reduce/simple (f list accum)
  (if (null list)
      accum
    (reduce/simple f (rest list) (funcall f accum (first list)))))

（同样，这不是很自然的 CL 代码，因为它依赖于尾调用消除来处理大型列表，但它表明您可以在没有赋值的情况下执行此操作。）

所以现在我们可以编写 insertion-sort 的最终版本：

(defun insertion-sort (l)
  (reduce/simple (lambda (a e)
                   (insert e a))
                 l '()))

并且很容易检查它是否也有效。

Common lisp中的插入排序

Insertion Sort in Common lisp

lisp

clisp

common-lisp