这就是我所做的:
(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 个元素，这也可能效率极低。
也许我走错了方向。你能给我一些建议吗？
最佳答案
真正的快速排序在 random-access 上运行数组，具有就地分区。例如see this .
您可以首先使用 list->vector 将列表转换为向量，然后以 C 方式通过使用变异交换对向量进行分区来实现快速排序。
随机化很容易:只需随机选择一个位置，然后在每个分区步骤之前将其内容与要排序的范围内的第一个元素交换。完成后，使用 vector->list 将其转换回来。
快速排序的有效实现可以在没有递归的情况下运行，在一个循环中，维护一个较大部分边界的堆栈，总是在较小的部分上递减(然后，当在底部时，切换到堆栈中的第一部分)。三向分区总是更可取的，一次处理等于。
您的基于列表的算法实际上是一个未解开的 treesort .
另见:
关于performance - 我可以使用 Scheme 有效地实现快速排序吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20688957/