我想在 clisp 中编写插入排序和合并排序。输入将是一个平面的数字列表。如何递归地编写这两种类型(最好不使用 lambda)?对于插入排序,我正在考虑创建一个函数,该函数将列表和整数(这意味着感兴趣的元素的当前索引)作为参数,并使用 setf 和 nth 来操作列表。我知道其中还应该有另一个递归函数,但是就像......我只是对这么多要存储的函数和变量感到困惑。
对于合并排序,我完全不知道。
我想在 clisp 中编写插入排序和合并排序。输入将是一个平面的数字列表。如何递归地编写这两种类型(最好不使用 lambda)?对于插入排序,我正在考虑创建一个函数,该函数将列表和整数(这意味着感兴趣的元素的当前索引)作为参数,并使用 setf 和 nth 来操作列表。我知道其中还应该有另一个递归函数,但是就像......我只是对这么多要存储的函数和变量感到困惑。
对于合并排序,我完全不知道。
合并排序是自然递归的(任何分而治之的问题也是如此)
http://en.literateprograms.org/Merge_sort_(Lisp)
他们引用的插入排序实现有点反功能
http://en.literateprograms.org/Insertion_sort_(Lisp)
但是循环可以很容易地变成尾递归。
我看到这是一个老问题,但我也很想知道如何以 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)))
欢迎任何建议!