sorting - 冒泡排序 Common Lisp 错误

Question

我正在尝试在 Common Lisp 中实现冒泡排序，但我很难确定自己的方位。[见下文]是我到目前为止所得到的，据我所知，它遵循算法，但我收到错误“使用参数 () 调用未定义的函数 SORTED”。当我运行它时。我似乎找不到这是什么原因。

(defun bubble (lis)
  (let ((sorted nil) (j 0))
    (do () ((not sorted))
      (progn 
        (setf sorted t)
        (do (i j (+ i 1))
            (if (< (nth i lis) (nth (+ i 1) lis))
                (progn
                  (swap1 (lis (nth i lis) (nth (+ i 1) lis)))
                  (setf sorted nil)
                  )
              )
          )
        )
      )
    )
  )

Answer 1

每次调用 NTH 都需要迭代该列表。如果将列表视为向量，则可能应该使用向量。如果您并不真正关心效率，您可能仍然想使用 ELT而不是 NTH，因为 ELT 适用于任何类型的序列。这样，您可以传递向量或列表，并且至少其中一个可以很好地工作(就冒泡排序的效率而言)。您最终可能会得到类似Rosetta Code中的东西。 .

顺便说一句，Rosetta Code 有一个列表迭代冒泡排序的示例，所以我不会复制它。相反，下面是我改编自 Prolog 的递归版本。之一(罗曼·巴塔克)。因此，它不一定更好，但它使用多个值，ETYPECASE，DESTRUCTURING-BIND，...显然通常不教授的功能。

(defun bubble-sort (list)
  (labels
      ((bsort (list acc)
         (etypecase list
           (null acc)
           (cons (destructuring-bind (head . tail) list
                   (multiple-value-bind (new-tail max)
                       (bubble head tail)
                     (bsort new-tail
                            (cons max acc)))))))
       (bubble (x list)
         (etypecase list
           (null (values nil x))
           (cons (destructuring-bind (y . tail) list
                   (multiple-value-bind (new-tail max)
                       (bubble (max x y) tail)
                     (values (cons (min x y) new-tail)
                             max)))))))
    (bsort list nil)))