在Clisp中排序

Question

我想在clisp中写入插入排序和合并排序。输入将是一个数字的平面列表。如何递归地写这2种（最好不使用lambdas）？对于插入排序，我正在考虑制作一个函数，该函数将列表和一个整数（这意味着作为感兴趣的元素的当前索引）作为参数，并使用setf和nth来操作列表。我知道那里面也应该有另一个递归函数，但是就像...我只是被这么多的函数和变量混淆了，以至于无法存储。

对于合并排序我绝对不知道。

Answer 1

归并排序自然是递归的（因为任何分而治之的问题）

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

他们都引用插入排序的实现是那种防功能

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

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

Answer 2

我看到这是一个老问题，但我也courious如何编写Common Lisp的风格的递归实现归并，所以我写了这种方式：

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

任何建议都欢迎！