LISP 合并两个整数列表并按升序对它们进行排序？

Question

我在合并列表时没有问题，但按升序对它们进行排序是我很费劲的地方。

 (define (combineASC l1 l2)
   (cond 
     ((null? l1) l2)
     (#t (cons (car l1) (combineASC (cdr l1) l2)))
     (sort l2 #'<))) ; I found this part in an online source

这是我得到的输出:

(combineASC '(2 4 6) '(1 4 5))

(2 4 6 1 4 5)

有人对我有什么建议吗？

Answer 1

因此，您要组合两个输入列表，每个列表都已按升序排序。您想将它们“编织”成一个，也按升序排列。

为此，您只需获取两个头元素(每个元素都来自每个输入列表)并进行比较；然后你从它的列表中取出最小的，并进一步组合你剩下的 - 使用相同的功能。

不会涉及排序。根据定义它的过程，结果列表已经排序。

此操作通常称为“合并”。它保留重复项。它的重复删除对应物，也将两个有序列表合并为一个，被称为“联合”。这是因为这些有序(非降序，或严格升序)列表可以被视为集合的表示。

---

另一个需要注意的微妙之处是，当两个 head 元素相等时要做什么。是的，我们已经决定保留重复项，但是两个中先删除哪个？

通常是左边那个。然后当这样定义的 merge 操作被用作 merge sort 的一部分时，排序将是稳定的(当然必须正确定义分区也为此)。稳定意味着，元素的原始顺序被保留。

例如，如果排序是稳定的，当按对的第一个元素排序时，(3,1) (1,2) (3,3) 保证排序为 (1,2) (3,1) (3,3) 而不是 (1,2) (3,3) (3,1)。

因此，按照您的代码框架，我们得到

;; combine two non-decreasing lists into one non-decreasing list,
;; preserving the duplicates
(define (combineNONDECR l1 l2)
   (cond 
     ((null? l1) l2)
     ((null? l2) l1)
     ((<= (car l1) (car l2))
      (cons (car l1) (combineNONDECR (cdr l1) l2)))
     (t
      (cons (car l2) (combineNONDECR l1 (cdr l2))))))

但如果您真的需要结果按升序排序，而不是非递减，那么您必须稍微调整一下 - make = 大小写分开，并单独处理，以防止重复出现(每个升序列表中没有重复，但列表可能包含两者之间的一些重复).