1

该函数仅适用于正数。有时会使用负数，但大多数时候会显示此错误“值 -1 不是 UNSIGNED-BYTE 类型”。

(defun OrdRapido (lista inf sup)
  (let ((pivote (nth sup lista)) (i (1- inf)) (j sup) (aux))
    (unless (>= inf sup)
        (loop (when (>= i j) (return))
          (loop (setf i (1+ i)) (when (>= (nth i lista) pivote) (return)))
          (loop (setf j (1- j)) (when (<= (nth j lista) pivote) (return)))
          (when (< i j)
            (setf aux (nth i lista))
            (setf (nth i lista) (nth j lista))
            (setf (nth j lista) aux)))  
        (setf aux (nth i lista))
        (setf (nth i lista) (nth sup lista))
        (setf (nth sup lista) aux) 
        (OrdRapido lista inf (1- i))
        (OrdRapido lista (1+ i) sup)) 
    lista))

例如：

(setq lista2 '(-5 3 7 6 2 1 -4 100 5 80 96 14 2 3 1 0 0 789 -1 3))
(OrdRapido lista2 0 (1- (length lista2)))

CL-USER> 
(-5 3 7 6 2 1 -4 100 5 80 96 14 2 3 1 0 0 789 -1 3)
CL-USER> 
(-5 -4 -1 0 0 1 1 2 2 3 3 3 5 6 7 14 80 96 100 789)

但不适用于此，我只将 - 添加到 80

'(-5 3 7 6 2 1 -4 100 5 -80 96 14 2 3 1 0 0 789 -1 3)

谢谢

修正版（随机添加），我知道有更好的方法，这只是教授留下的练习

 (defun OrdRapido (lista inf sup)
  (let ((pivote (nth (random (1+ sup)) lista)) (i inf) (j sup) (aux))
    (unless (>= inf sup)
        (loop (when (> i j) (return))
          (loop (when (<= (nth i lista) pivote) (return)) (setf i (1+ i)))
          (loop (when (>= (nth j lista) pivote) (return)) (setf j (1- j)))
          (when (<= i j)
            (setf aux (nth i lista))
            (setf (nth i lista) (nth j lista))
            (setf (nth j lista) aux)
            (setf i (1+ i))
            (setf j (1- j))))  
        (OrdRapido lista inf j)
        (OrdRapido lista i sup)) 
    lista))
4

3 回答 3

6

您正在尝试返回不起作用的列表的第 -1 个元素。nth 返回列表的第 n 个元素，因此 (nth 0 '(1 2 3)) 将返回 1。但在您的代码中的某个时刻，它调用 (nth -1 (-5 -80 -4 -1 0 0 ... )) 和繁荣！

关于您的代码的其他说明：

  • 将结束 ) 放在单独的行上不是好的 lisp 样式，并且会使您的代码更难阅读。Lisp 代码由列表组成，括号并不像其他语言的花括号。
  • 使用支持您的语言的编辑器。我推荐带有 Slim 的 Vim 或带有 slime 的 Emacs。如果您将 emacs 与 slime 一起使用，此视频可能会帮助您入门。
  • 不要在你的名字中使用骆驼外壳。所有符号在实习时都以普通 lisp 的形式大写，因此'HelloThere与'hellothere或' HELLOTHERE完全相同

也请查看快速排序的rosettacode 页面，了解如何用common-lisp（以及许多其他语言）进行处理。

;; Here is a functional version for example.
(defun quicksort (list &aux (pivot (car list)) )
  (if (rest list)
      (concatenate 'list 
             (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
             (remove-if-not #'(lambda (x) (= x pivot)) list)
             (quicksort (remove-if-not #'(lambda (x) (> x pivot)) list)))
      list))

如果您不习惯阅读 lambda，那么这里的代码与上面的代码相同，但将 lambdas 制成了本地函数，因此代码读起来更像英语。

(defun quicksort (list &aux (pivot (car list)))
  (labels ((less-than-pivot (x) (< x pivot))
           (greater-than-pivot (x) (> x pivot))
           (equal-to-pivot (x) (= x pivot)))
    (if (rest list)
        (concatenate 'list 
                     (quicksort (remove-if-not #'less-than-pivot list))
                     (remove-if-not #'equal-to-pivot list)
                     (quicksort (remove-if-not #'greater-than-pivot list)))
        list)))

在我看来，第二个版本不太整洁。在这两个示例中，您可以看到递归方法如何让您考虑如何只做一步，然后通过调用自身，您将解决方案应用于一步以获得整个问题的解决方案

于 2013-08-30T10:50:05.513 回答
1

只是因为您最初的想法是使用loop. 以下是您可能已完成的操作：

(defun quicksort (list)
  (if (cdr list)
      (loop :with pivot := (car list)
         :for element :in list
         :if (< element pivot) :collect element :into a
         :else :if (= element pivot) :collect element :into b
         :else :collect element :into c
         :finally (return (nconc (quicksort a) b (quicksort c)))) list))
于 2013-08-30T12:19:27.967 回答
1

除了编译器技巧，NTH 需要 O(i) 时间来访问列表的第 i 个元素，因为它必须遍历列表中的每个元素直到该点。这意味着仅使用 NTH 访问列表的每个元素将花费 O(n^2) 时间。由于快速排序应该在 O(nlgn) 时间内执行，因此需要稍作改动。

通过在遍历列表时抓住剩余的尾部并通过该尾部而不是使用 NTH 访问，您可以对列表进行快速排序。由于 lisp 列表是单链接的，因此还必须仅向前遍历列表。

(defun simple-list-partition (list end)
  "Reorder list until end such that all values less than the first value in the
  list are placed left of it and all greater placed to its right; return the new
  index of the first value and the tail of the list starting with that value as
  multiple values."
  (loop for walk-cons on (cdr list)
        for walk-value = (car walk-cons)
        for walk-index from 1
        with pivot-value = (car list)
        with rotate-cons = list
        with rotate-index = 0
        while (<= walk-index end)
        when (< walk-value pivot-value)
        do (progn (setq rotate-cons (cdr rotate-cons)
                        rotate-index (+ 1 rotate-index))
                  (rotatef (car rotate-cons) (car walk-cons)))
        finally (progn (rotatef (car list) (car rotate-cons))
                       (return (values rotate-index rotate-cons)))))

(defun quicksort (list)
  "Quicksort for lists."
  (labels ((quicksort% (l  max)
             (when (and (plusp max) (cdr l))
               (multiple-value-bind (index tail)
                   (simple-list-partition l max)
                 (quicksort% l (1- index))
                 (quicksort% (cdr tail) (- max index 1))))))
    (quicksort% list (1- (length list)))
    list))

为简单起见，上述内容并不能防止在预排序或相等元素的列表上表现不佳。

于 2013-09-03T02:30:52.843 回答