难以为归并排序编写 LISP 递归函数

Question

您好，我有一个问题，我在解决时遇到了一些困难，请参见下文

使用函数SPLIT-LIST和MERGE-LISTS定义递归 Lisp 函数 MSORT 使得如果 L 是实数列表，则 (MSORT L) 是由 L 的元素按升序排列组成的列表。在 MSORT 的定义中，您可以调用 SPLIT-LIST， MSORT 本身、MERGE-LISTS、CAR、CDR、CADR 和 ENDP，但您不应调用任何其他功能。务必使用 LET 或 LET*，这样 MSORT 只调用一次 SPLIT-LIST。

到目前为止，我能够正确编写 SPLIT-LIST 和 MERGE-LISTS 函数，但是对于 M-SORT，我在编写函数时遇到了困难。到目前为止，请参见下面的所有三个定义。任何有关如何按照问题中的指南正确编写 MSORT 函数的帮助，我们将不胜感激。

(defun SPLIT-LIST (L)
  (if (endp L)
      '(nil nil)
    (let ((X (split-list (cdr L))))
      (list  (cons (car L)(cadr X)) (car X) ))))

(defun MERGE-LISTS (L1 L2)
  (cond
   ((and(endp L1 )(endp L2)) nil )
   ((endp L1) (cons (CAR L2) (MERGE-LISTS nil (CDR L2))))
   ((endp L2) (cons (CAR L1) (MERGE-LISTS (CDR L1) NIL)))
   ((< (CAR L1) (CAR L2)) (cons (CAR L1) (MERGE-LISTS (CDR L1) L2  )))  
   ((>= (CAR L1) (CAR L2)) (cons (CAR L2) (MERGE-LISTS L1 (CDR L2))  ))))

(defun MSORT (L)
  (cond ((endp L ) nil)
        ( (equal (Length L) 1) L)
        (T
         (let* (
                (S (SPLIT-LIST L ))
                (L1 (CAR S))
                (L2 (CADR S))
                (X (MSORT (cdr L1)))
                (Y (MSORT (cdr L2)))


                )
           (MERGE-LISTS 
            (if (and (numberp (car L1)) (numberp (car X))(<=  (car L1 ) (car X)))  
                (list (car L1) (car X))
              (list (car X) (car L1) )
              ) 

            (Cons (car L2) Y))

           )))
  )

Answer 1

你把它复杂化了。您不需要对 SPLIT-LIST 返回的子列表的 CDR 进行排序，只需对整个列表进行排序，然后合并它们即可。

(defun MSORT (L)
  (cond ((endp L) nil)
        ((endp (cdr L)) L)
        (t
         (let* ((S (SPLIT-LIST L ))
                (L1 (car S))
                (L2 (cadr S))
                (X (MSORT L1))
                (Y (MSORT L2)))
           (MERGE-LISTS X Y)))))

难以为归并排序编写 LISP 递归函数

Difficulty writing LISP Recursive Function for Merge Sort

lisp

common-lisp