时间戳

首页 > 解决方案 > Common lisp 中的插入排序

lisp - Common lisp 中的插入排序

问题描述

我想用这个 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（非排序列表）

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

不使用赋值，使用 INSERT 函数

标签： lispcommon-lispclisp

解决方案

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

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

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

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

  • 遍历要排序的列表：
    • 对于每个元素，将其插入排序列表；
    • 最后返回排序列表。

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

好吧，有一个标准的技巧来做这种事情，那就是使用带有累加器参数的尾递归函数，它会累加结果。我们可以将此函数编写为显式辅助函数，也可以将其设为局部函数。我将做后者，因为没有理由让仅在本地使用的函数全局可见，并且因为（因为我假设这是家庭作业）它使得直接提交变得更加困难。

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

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

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

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

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

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

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

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

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

是相同的

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

cons如果您使用as 函数，这更容易看出：

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

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

好吧，当然，insert如上定义的，真的很适合这个：它接受一个有序列表并将一个新的对插入其中，返回一个新的有序列表。有两个问题：

  • myinsert以错误的顺序接受它的论点（这可能是原来的以另一种顺序接受论点的原因！）；
  • 需要有一种“播种”初始排序列表的方法，即().

好吧，我们可以通过重写来修复错误的参数顺序insert，或者只是将它包装在一个交换参数的函数中：我会做后者，因为我不想重新访问我上面写的内容，我不想想要两个版本的功能。

您可以通过将初始空值添加到要排序的事物列表中来“播种”初始空值，或者实际上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 '()))

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

推荐阅读