0

我正在Scheme中编写合并排序。我有一个合并排序定义、一个拆分列表的拆分器和一个合并列表的合并。

(define mymergesort
  (lambda (alist)
    (if (null? (cdr alist)) alist
        (let ((splits (splitter alist)))
          (merge (mymergesort (car splits)) (mymergesort (cadr splits)))))))

(define splitter
  (λ (alist) (splitter-helper alist () ())))

(define splitter-helper
  (λ (alist list_a list_b)
    (cond ((null? alist) (cons (reverse list_a) (cons list_b ())))
          ((null? (cdr alist)) (cons (reverse (cons (car alist) list_a)) (cons list_b ())))
           (else (splitter-helper (reverse (cdr (reverse (cdr alist)))) (cons (car alist) list_a) (cons (car (reverse (cdr alist))) list_b))))))

(define merge
  (λ (list_a list_b)
    (cond ((null? list_a) list_b)
          ((null? list_b) list_a)
          ((<= (car list_a) (car list_b)) (cons (car list_a) (merge (cdr list_a) list_b)))
          ((<= (car list_b) (car list_a)) (cons (car list_b) (merge list_a (cdr list_b)))))))

这个实现似乎可以很好地对数字列表进行排序。但我希望能够对混合元素列表进行排序。

例如：'（我可以“去”4“大约”123苏打水k？）

有什么建议/解决方案吗？我还试图避免使用大多数过程，例如围绕递归解决方案“欺骗”的长度。

4

1 回答 1

1

您需要一个对这些项目进行排名的“启发式”。例如，“go”是否在“about”之前？4个呢？因此，您可以编写一个函数来确定要排序的一个元素是否是另一个元素的 '<='。还，

(<= (car list_a) (car list_b))然后(<= (car list_b) (car list_a))有点多余。如果 a 不是 <= b，那么我们知道 a > b。

于 2013-02-08T11:13:28.277 回答