list - 根据 Scheme 中的第二个元素对对列表进行排序

Question

有人可以给我一些建议，告诉我如何编写代码以根据每对的第二个元素按升序对一对列表进行排序吗？我没有给你一个例子，但这似乎是一件容易想象的事情。

Answer 1

让我们尝试编写一个归并排序。

(define (mgsort ls cmp)
  (cond
    ((or (null? ls) (null? (cdr ls)))
       ls)
    ; right? ... then,
    (else 
      (split ls '() '() cmp))))

处理列表的最基本工具是结构递归：

(define (split ls a b cmp)
  (cond 
    ((null? ls) 
       (merge (mgsort a cmp) (mgsort b cmp) cmp))
    (else
       (split (cdr ls) b (cons (car ls) a) cmp))))

现在剩下的就是写merge——一个将合并的函数，比如“zipping”，它的两个参数是排序列表，所以结果也是一个排序列表。

(define (merge a b cmp)
  (cond 
    ((null? a) b)
    ((null? b) ....)
    ((cmp (car a) (car b))   ; right?
       (cons   
          ... ;; what? ... with what??
          (merge (cdr a) ......)))
    (else
       (cons
          ... 
          (merge a ......)))))

测试：

(mgsort (list 3 1 5 4 6 2 3) <)
;Value 12: (1 2 3 3 4 5 6)

(mgsort (list (cons 3 1) (cons 4 5) (cons 6 2)) (lambda(a b) (< (cdr a) (cdr b))))
;Value 13: ((3 . 1) (6 . 2) (4 . 5))

---

参看。如何使用递归合并两个在 lisp 中按字母顺序排列的字符串，以实现高效的自上而下的合并功能（尽管在 Common Lisp 中，名义上是字符串，但它确实适用于内部列表），尾递归的手动实现模数优化技术。