这就是我所做的：
(define qsort
(lambda (l)
(let ((lesser '()))
(let ((greater '()))
(cond
((null? l) '())
(else (map (lambda (ele)
(if (> (car l) ele)
(set! lesser (cons ele lesser))
(set! greater (cons ele greater)))) (cdr l))
(append (qsort lesser) (cons (car l) (qsort greater))))
)))))
我注意到，当提供一个已经排序的列表时，它会变得非常缓慢。经过一番搜索，我发现如果以随机的方式选择"枢轴"，性能可以提高。然而，我知道实现这一点的唯一方法是list-ref，它似乎是O(n)。更糟糕的是，我必须实现一个类似cdr的函数来删除列表中的第n个元素，这可能也非常低效。
也许我走错了方向。你能给我一些建议吗？
true quicksort在随机访问数组上运行，带有就地分区。例如，请参阅此。
您可以先用list->vector将列表转换为向量，然后用C方式通过使用可变交换对向量进行分区来实现快速排序。
随机化它很容易：只需随机选择一个位置，并在每个分区步骤之前，将其内容与要排序的范围中的第一个元素交换。完成后，使用vector->list将其转换回。
快速排序的有效实现可以在没有递归的情况下运行，在一个循环中，保持一堆较大的部分边界，总是从较小的部分开始(然后，在底部时，切换到堆栈中的第一个部分)。三向划分总是更可取的，一次性处理相等的问题。
您的基于列表的算法实际上是一个分解的树排序。
另请参阅：
- http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell
- 伪快速排序时间复杂性
虽然已经有了一个公认的答案，但我想你可能会欣赏the Pitmanual中绵羊把戏的Scheme翻译。您的代码实际上已经与它非常相似了。Scheme确实支持do循环，但它们不是特别惯用，而命名的let更常见，所以我在本代码中使用了后者。正如您所注意到的，如果列表已经排序，那么选择第一个元素作为枢轴会导致性能问题。由于您必须在每次迭代中遍历列表，因此您可以做一些聪明的事情来提前为递归调用选择左侧和右侧的枢轴。
(define (nconc l1 l2)
;; Destructively concatenate l1 and l2. If l1 is empty,
;; return l2. Otherwise, set the cdr of the last pair
;; of l1 to l2 and return l1.
(cond
((null? l1)
l2)
(else
(let loop ((l1 l1))
(if (null? (cdr l1))
(set-cdr! l1 l2)
(loop (cdr l1))))
l1)))
(define (quicksort lst)
(if (null? lst) lst
(let ((pivot (car lst))
(left '())
(right '()))
(let loop ((lst (cdr lst))) ; rebind to (cdr lst) since pivot wasn't popped
(if (null? lst)
(nconc (quicksort left)
(cons pivot
(quicksort right)))
(let ((tail (cdr lst)))
(cond
((< (car lst) pivot)
(set-cdr! lst left)
(set! left lst))
(else
(set-cdr! lst right)
(set! right lst)))
(loop tail)))))))
(quicksort (list 9 1 8 2 7 3 6 4 5))
;=> (1 2 3 4 5 6 7 8 9)
Scheme确实支持do，所以如果你对此感兴趣(它确实使Common Lisp和Scheme版本非常相似)，它看起来是这样的：
(define (quicksort lst)
(if (null? lst) lst
(do ((pivot (car lst))
(lst (cdr lst)) ; bind lst to (cdr lst) since pivot wasn't popped
(left '())
(right '()))
((null? lst)
(nconc (quicksort left)
(cons pivot
(quicksort right))))
(let ((tail (cdr lst)))
(cond
((< (car lst) pivot)
(set-cdr! lst left)
(set! left lst))
(else
(set-cdr! lst right)
(set! right lst)))
(set! lst tail)))))
(display (quicksort (list 9 1 8 2 7 3 6 4 5)))
;=> (1 2 3 4 5 6 7 8 9)
真正高效的Quicksort实现应该到位，并使用可以通过索引高效访问的数据结构来实现，这使得不可变链表成为一个糟糕的选择。
问题是，快速排序是否可以通过Scheme有效地实现——答案是肯定的，只要你不使用列表。切换到使用vector，它是可变的，并且可以对其元素进行基于O(1)索引的访问，就像类C编程语言中的数组一样。
如果你的输入数据在一个链表中，你总是可以这样做，这可能比直接排序列表更快：
(define (list-quicksort lst)
(vector->list
(vector-quicksort ; ToDo: implement this procedure
(list->vector lst))))