scheme - 对方案中的列表进行排序

Question

我想创建对列表进行排序的函数。例如我有这个列表：

x1, x2, x3 .... xn

或者

1, 2, 3, 4, 5, 6

我想按以下顺序显示数字：

x1, xn, x2, xn-1

或者

1, 6, 2, 5, 3, 4

你能帮我写这个例子吗？

Answer 1

通常当我们谈论排序时，我们指的是根据项目内容的一些特征对项目进行排序，而不是项目在列表中的位置。我会称您的情况为置换，但也许有些人也会对这种用法提出异议。:-)

以下是您解决问题的方法：

1. 在中间拆分列表（如果您只想遍历列表一次，可以使用 tortoise-and-hare 执行此操作）；如果需要，请调用这些列表head和。tail
2. 反转tail列表，并将其与head列表交错。

另一种方法：

1. 反转原始列表对（我们称之为rev）。
2. 将原始列表与 交错rev，跟踪每次遍历的元素。当他们在中间相遇时，停下来。

这是第二种方法的演示（需要加载SRFI 1）：

(define (zippy lst)
  (if (null? lst)
      '()
      (let recur ((lst lst)
                  (rev (pair-fold cons '() lst)))
        (cond ((eq? lst (car rev)) (list (car lst)))
              ((eq? (cdr lst) (car rev)) (list (car lst) (caar rev)))
              (else (cons* (car lst) (caar rev)
                           (recur (cdr lst) (cdr rev))))))))

Answer 2

这并不是真正的排序操作，更像是洗牌；这是解决它的另一种方法。首先，让我们定义interleave从两个列表中交替元素的过程，返回一个列表：

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

现在我们取原始列表和split-at中间（这是一个特定于 Racket 的过程）；最后我们交错两个结果列表，反转尾部：

(define (zippy lst)
  (let-values (((head tail) (split-at lst (quotient (length lst) 2))))
    (interleave head (reverse tail))))

恕我直言，上面的实现更直观一些，如果您使用的是 Racket，它不需要外部库。它按预期工作：

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