方案：不使用set等命令性功能更新列表

Question

我才刚刚开始学习方案，并被要求在方案中实现快速排序算法，但我们不允许使用任何命令性功能，例如set!，也不允许我们使用filter

我已经考虑了这一点，想出自己的算法，但是我似乎无法避免使用set!来更新列表：

(define quicksort
(lambda (L)
    (cond
        [(or (null? L) (null? (cdr L))) L]
        [else (let ((pivot (car L)) (small '()) (large '()))
                   (do ((i (- (length L) 1) (- i 1)))
                       ((= i 0))
                           (if (< (list-ref L i) pivot)
                               (set! small (cons (list-ref L i) small))
                               (set! large (cons (list-ref L i) large))))
                           (append (quicksort small) (list pivot) (quicksort large)))])))

此代码有效，但是有没有办法使用列表来更新列表small和large？

Answer 1

如果无法使用set!，则无法更改列表。系统会要求您在功能上进行此操作，而无需进行任何更改。无需就地修改列表，而是建立较小的，部分排序的列表，然后在保留排序的同时将它们合并。

Answer 2

公平地说，快速排序是一种就地算法，许多人会声明将向量替换为列表将对其进行足够的更改，以使其不再成为蜜蜂快速排序。此刻，我将忽略这一点。

将较大的内容拆分为较小的代码块。这样，您可以测试每个步骤：

(segment 5 '(5 1 1 3 8 6 4 9 8 5 3 5 3 8 6))
; ==> ((1 1 3 4 3 3) (5 5) (8 6 9 8 8 6))

当然，您首先要进行简单的测试：

(segment 5 '(5)) ; ==> (() (5) ())
(segment 5 '(5 1)) ; ==> ((1) (5) ())
(segment 5 '(5 8)) ; ==> (() (5) (8))
(segment 5 '(5 8 1 5)) ; ==> ((1) (5 5) (8))

子列表中结果的顺序并不重要。例如。结果((3 3 4 3 1 1) (5 5) (6 8 8 9 6 8))同样足够，并且很可能更容易做到。

[首先通过检查是否小于2个元素列表将其作为quicksort。 (or (null? lst) (null? (cdr lst)))并返回参数，或使用第一个元素作为枢轴，然后创建[3个段]，然后append递减较小和较高的位置，然后将3个列表附加在一起，然后按顺序排列它们。

作为灵感，这是一个在奇数上分裂的过程？而不是：

(define (split-odd lst)
  (let loop ((lst lst) (odd '()) (even '()))
    (cond
      ((null? lst) (list odd even))
      ((odd? (car lst)) (loop (cdr lst) (cons (car lst) odd) even))
      (else (loop (cdr lst) odd (cons (car lst) even)))))
(split-odd '(1 2 3 4 5 6))
; ==> ((5 3 1) (6 4 2))