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

任何建議都歡迎！