2

我在方案中实现合并排序，我必须通过定义两个辅助方法来实现：合并和拆分。

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

拆分方法让我很难过。我找到了一个用两种不同的方法（“奇数”和“偶数”）完成此操作的示例，但我想知道是否有一种方法可以将它们组合成一个称为“拆分”的方法？

此处找到的示例：方案中的合并排序

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

4

1 回答 1

3

一个简单的split实现，适合用作 a 的一部分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。

于 2012-11-13T01:08:07.670 回答