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. 在中间拆分列表(如果你只想遍历列表一次，你可以使用龟兔赛跑来做到这一点)；如果需要，可以将这些列表称为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))))))))