如何改进方案中的这种归并排序？

Question

我是C ++程序员，我编写了此代码，以查看我是否可以在功能上思考:)有没有提示改进它？

(define (append listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    (else (cons (car listOne) (append (cdr listOne) listTwo)))))

(define (merge listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    ((null? listTwo) listOne)
    ((< (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    ((= (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    (else (append (cons (car listTwo) '())
                  (merge listOne (cdr listTwo))))))

(define (mergesort lis)
  (cond
    ((null? lis) '())
    ((null? (cdr lis)) lis)
    (else (merge (cons (car lis) '())
                 (mergesort (cdr lis))))))

(mergesort '(99 77 88 66 44 55 33 11 22 0))

Answer 1

我只看到一个小改进：

(append (cons (car listTwo) '())
              (merge listOne (cdr listTwo))))

处处都可以简化为

(cons (car listTwo)
      (merge listOne (cdr listTwo)))

我认为你正在考虑类似的东西（用 Python 式的语法）：

[car(listTwo)] + merge(listOne, cdr(listTwo))

但是 cons 直接将一个项目添加到列表的前面，就像函数一样 push, ，所以就像下面的代码：

push(car(listTwo), merge(listOne, cdr(listTwo)))

最终，额外的附加只会导致每个项目的双 con 单元分配，所以这不是什么大问题。

另外，我认为如果你做到了，你可能会获得更好的表现 mergesort 更有趣的是，它可以保持列表长度并在每一步对列表的两半进行排序。不过，这可能不适合这样的学习示例。

就像是：

(define (mergesort l)
  (let sort-loop ((l l) (len (length l)))
    (cond
      ((null? l) '())
      ((null? (cdr l)) l)
      (else (merge (sort-loop (take (/ len 2) l) (/ len 2)))
                   (sort-loop (drop (/ len 2) l) (/ len 2)))))))))
(define (take n l)
  (if (= n 0)
      '()
      (cons (car l) (take (sub1 n) (cdr l)))))
(define (drop n l)
  (if (= n 0)
      l
      (drop (sub1 n) (cdr l))))

Answer 2

在一般情况下，mergesort是做了很多的列表操作，因此它是好得多破坏性做事情的“就地”排序子部分。你可以看到在PLT的计划的实施sort的例如共同的代码，它起源于SLIB。 （它看起来吓人上一见倾心，但如果你读了评论，而忽略旋钮和优化，你会看到它都在那里。）

此外，你应该看看 SRFI-32 以分拣的扩展讨论接口