方案:如何将列表拆分为奇数条目和偶数条目的两个列表？

Question

我在scheme中实现合并排序，我必须通过定义两个辅助方法来实现:merge和split。

Merge 需要两个列表(已经按递增顺序)并将它们合并在一起。我这样做了如下:

(define merge 
   (lambda (list1 list2)
       (if (null? list1)
          list2
             (if (null? list2)
                list1
                   (if (< (car list1) (car list2))
                      (cons (car list1) (merge (cdr list1) list2))
                      (cons (car list2) (merge (cdr list2) list1)))))))

拆分方法让我难住了。我找到了一个例子，它用两种不同的方法(“奇数”和“偶数”)来实现这一点，但我想知道是否有办法将它们组合成一个称为“拆分”的方法？

示例在这里找到: merge sort in scheme

我显然对计划很陌生，谁能帮我了解如何做到这一点？

Answer 1

一个简单的split实现，适合用作 mergesort 的一部分，如下:

(define (split lst)
  (let ((half (quotient (length lst) 2)))
    (list (take lst half)
          (drop lst half))))

它将输入列表分成两半，在列表列表中返回它们 - 第一个列表对应于输入列表的前半部分，第二个列表对应于输入列表的后半部分。

根据问题的要求，另一种选择是将列表拆分为奇数/偶数元素，如下所示:

(define (split lst)
  (list (filter odd? lst)
        (filter even? lst)))

另一种选择，通过使用 partition您可以一次性拆分输入列表:

(define (split lst)
  (let-values (((odds evens) (partition odd? lst)))
    (list odds
          evens)))

请注意，仅当输入列表仅包含整数时，最后两个替代方法才有用，用于使用您自己的 mergesort 实现对其他数据类型的列表进行排序。 ，你最好使用我的第一个版本 split .