2

我正在Scheme中编写合并排序，我很好奇为什么这不起作用......

这是我希望工作的实现，但没有：

(define (mergesort op l)
  (cond ((null? l) l)
      ((null? (cdr l)) l)
      (else (merge op (car l)
                      (mergesort op (cdr l))))
  )
)

这是“正确”的实现。

(define (mergesort op l)
  (cond ((null? l) l)
      ((null? (cdr l)) l)
      (else (merge op (cons (car l) (list))
                      (mergesort op (cdr l))))
  )
)

为什么我必须 (cons (car l) (list)) 在尝试将其与递归合并之前？

4

2 回答 2

4

请注意：

(cons (car l) (list))

... 相当于：

(list (car l))

换句话说，您必须传递一个包含单个元素的列表，而不仅仅是一个元素作为merge过程的第二个参数。

于 2013-02-01T22:56:06.220 回答
2

奥斯卡是完全正确的，但有一点被忽视了。

这不是归并排序。归并排序的定义是什么？它获取列表，将其分成两半，对每个排序列表进行排序，然后将它们合并在一起。

你没有分成两半；你分裂成一个和其余的。然后对其余的进行排序，并将单个元素合并到列表中。但是您可以将单个元素合并到列表中视为将元素插入到列表中。

啊哈，有线索！您已经编写了插入排序。哪个很好；有用。它的效率要低得多。

因此，归并排序和插入排序之间的区别在于选择了错误的位置来拆分列表。

于 2013-02-01T23:36:01.847 回答