0

组合列表没有问题，但按升序对它们进行排序是我苦苦挣扎的地方。

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

有人对我有什么建议吗？

4

3 回答 3

4

因此，您正在组合两个输入列表，每个列表都已按升序排序。你想把它们“编织”成一个，也是按升序排列的。

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

将不涉及排序。结果列表将根据定义它的过程进行排序。

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

另一个需要注意的微妙之处是，当两个头部元素相等时该怎么办。我们已经决定保留副本，是的，但是要先取出两个中的哪一个？

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

例如，如果排序是稳定的，那么当按pairs的第一个元素排序时，(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))))))

但是，如果您真的需要结果按升序排列，而不是non-decreshing，那么您必须稍微调整一下 - 将=案例分开并单独处理，以阻止重复项潜入（每个升序列表中没有重复项，但列表可能包含它们两者之间的一些重复项）。

于 2012-10-04T18:15:47.463 回答
1

因为尾递归:)

(define (merge-sorted . lists)
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted
                  (sort tails
                        (lambda (a b)
                          (<= (car a) (car b))))))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted) (cdr sorted)))))))
  (reverse (%merge-sorted '() lists)))

(merge-sorted '(1 2 3) '(4 5 6 7 8 9) '(2 4 6) '(1 3 5 7))
  • 它可以更好地扩展：P

我想这就是威尔所说的：

(define (merge-sorted . lists)
  (define (%swap-if-greater lists)
    (define (%do-swap head next built tails)
      (cond
       ((null? tails)
        (append (reverse built)
                (cond
                 ((null? next) (list head))
                 ((> (car head) (car next))
                    (list next head))
                 (else (list head next)))))
       ((> (car head) (car next))
        (%do-swap head (car tails)
                  (cons next built) (cdr tails)))
       (else (append (reverse built)
                     (list head) (list next) tails))))
    (%do-swap (car lists)
              (if (null? (cdr lists)) '() (cadr lists))
              '() (if (null? (cdr lists)) '() (cddr lists))))
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted (%swap-if-greater tails)))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted)
                                  (cdr sorted)))))))
  (reverse
   (%merge-sorted
    '() (sort lists (lambda (a b) (<= (car a) (car b)))))))

特别是考虑到 Schemes... 在布尔值上的有趣位置，我不会对此很感兴趣。

于 2012-10-05T00:43:12.020 回答
0 
(defun merge (l1 l2)
 (if (not (and (eql nil l1) (eql l2 nil))
  (if (> (car l1) (car l2))
     (cons (car l1) (merge (cdr l1) l2))
    (cons (car l2) (merge (cdr l2) l1)))
  ;;;append the not-nil string to the rest.
  )

这应该可以工作（您仍然需要完成代码，但想法很明确）

请注意，此代码在 common-lisp 中。

查找合并排序以获取有关该技术的更多信息

于 2012-10-04T18:17:01.430 回答