scheme - 如何对方案中的数字无序列表进行排序

Question

用Scheme中的值对列表进行排序的正确方法是什么？例如，我有未排序的值：

x1, x5, x32 .... xn

或者

3, 4, 1, 3, 4, .. 9

首先，我想通过增加数量来为它们显示并按以下顺序显示它们：

x1, xn, x2, xn-1

或者

1, 6, 2, 5, 3, 4

任何帮助都是有价值的。

Answer 1

这与您之前发布的问题相同，但略有不同。正如我在回答的评论中告诉你的那样，你只需要在重新排列之前对列表进行排序。这是一个球拍解决方案：

(define (interleave l1 l2)
  (cond ((empty? l1) l2)
        ((empty? l2) l1)
        (else (cons (first l1)
                    (interleave l2 (rest l1))))))

(define (zippy lst)
  (let-values (((head tail) (split-at
                             (sort lst <) ; this is the new part
                             (quotient (length lst) 2))))
    (interleave head (reverse tail))))

它按预期工作：

(zippy '(4 2 6 3 5 1))
=> '(1 6 2 5 3 4)

Answer 2

这是一种简单的尾递归方法，它使用“慢/快”技术在遍历一半列表时停止递归：

(define (interleave l)
  (let ((l (list-sort < l)))
    (let merging ((slow l) (fast l) (revl (reverse l)) (rslt '()))
      (cond ((null? fast)
             (reverse rslt))

            ((null? (cdr fast)) 
             (reverse (cons (car slow) rslt)))

            (else
             (merging (cdr slow) (cddr fast) (cdr revl)
                      (cons (car revl) (cons (car slow) rslt))))))))

Answer 3

这个 R6RS 解决方案符合 Chris Jester-Young 的建议，它确实是如何以糟糕的方式做到这一点。顺便说一句，Chris 和 Óscar 在同一个问题上没有排序的解决方案优于这个 zippy 程序。

    #!r6rs
    (import (rnrs base)
            (rnrs sorting)) ; list-sort

    (define (zippy lis)
      (let loop ((count-down (- (length lis) 1))
                 (count-up 0))
        (cond ((> count-up count-down) '())
              ((= count-up count-down) (cons (list-ref lis count-down) '()))
              (else (cons (list-ref lis count-down)
                          (cons (list-ref lis count-up)
                                (loop (- count-down 1)
                                      (+ count-up 1))))))))
    (define (sort-rearrange lis)
      (zippy (list-sort < lis)))

Answer 4

所以，你不介意慢，只想要一个基于选择的方法，是吗？开始了....

首先，我们定义一个select1获取最小（或最大）元素的函数，然后是所有其他元素。对于链表，这可能是最简单的方法，比尝试实现（比如）快速选择更容易。

(define (select1 lst cmp?)
  (let loop ((seen '())
             (rest lst)
             (ext #f)
             (extseen '()))
    (cond ((null? rest)
           (cons (car ext) (append-reverse (cdr extseen) (cdr ext))))
          ((or (not ext) (cmp? (car rest) (car ext)))
           (let ((newseen (cons (car rest) seen)))
             (loop newseen (cdr rest) rest newseen)))
          (else
           (loop (cons (car rest) seen) (cdr rest) ext extseen)))))

现在实际进行交织：

(define (zippy lst)
  (let recur ((lst lst)
              (left? #t))
    (if (null? lst)
        '()
        (let ((selected (select1 lst (if left? < >))))
          (cons (car selected) (recur (cdr selected) (not left?)))))))

这种方法是 O(n²)，而这里其他人推荐的排序和交错方法是 O(n log n)。