sorting - 在 Clip 中排序

Question

我想在 clisp 中编写插入排序和合并排序。输入将是一个平面的数字列表。如何递归地编写这两种类型（最好不使用 lambda）？对于插入排序，我正在考虑创建一个函数，该函数将列表和整数（这意味着感兴趣的元素的当前索引）作为参数，并使用 setf 和 nth 来操作列表。我知道其中还应该有另一个递归函数，但是就像......我只是对这么多要存储的函数和变量感到困惑。

对于合并排序，我完全不知道。

Answer 1

合并排序是自然递归的（任何分而治之的问题也是如此）

http://en.literateprograms.org/Merge_sort_(Lisp)

他们引用的插入排序实现有点反功能

http://en.literateprograms.org/Insertion_sort_(Lisp)

但是循环可以很容易地变成尾递归。

Answer 2

我看到这是一个老问题，但我也很想知道如何以 Common Lisp 风格编写 Mergesort 的递归实现，所以我这样写：

(defun mergesort (lo hi)
  (let ((mid 0)
  (items 0))

  ;; initializations
  (setq items (- hi lo))
  (multiple-value-bind (intreg rest)
  (floor (/ (+ hi (1+ lo)) 2))
    (setq mid intreg))

  ;; recursive call if more than 1 item
  (cond ((> items 1)
    (mergesort lo mid)
    (mergesort mid hi)))

  ;; merge step
  (let ((temp (sort-range *unsorted-list* lo mid hi)))
  (do ((x lo (1+ x))
   (tx 0 (1+ tx)))
  ((= x hi))
(setf (nth x *unsorted-list*) (nth tx temp))))
))

;; collect and sort range between low and high
(defun sort-range (LIST lo mid hi)
  (labels ((collect-range (i1 i2)
     (if (and (< i1 mid) (< i2 hi))
     (let ((lv (nth i1 LIST))
           (rv (nth i2 LIST)))

       (if(and (< lv rv) (< i1 mid))
          (cons lv (collect-range (1+ i1) i2))
          (if(<= i2 hi)
         (cons rv (collect-range i1 (1+ i2))))
          ))
     (if (< i1 mid)
         (cons (nth i1 LIST) (collect-range (1+ i1) i2))
         (if(< i2 hi)
        (cons (nth i2 LIST) (collect-range i1 (1+ i2)))))
     )))
(collect-range lo mid)))

欢迎任何建议！