这是一个用 Clojure 编写的数字快速排序算法。它基本上是在“The Joy of Clojure”，第 2 版，第 133 页中找到的快速排序算法。我稍微修改了它以（希望）更好的可读性，因为原始感觉有点太紧凑了：
(defn qsort-inner [work]
(lazy-seq
(loop [loopwork work]
(let [[ part & partz ] loopwork ]
(if-let [[pivot & valuez] (seq part)]
(let [ smaller? #(< % pivot)
smz (filter smaller? valuez)
lgz (remove smaller? valuez)
nxxt (list* smz pivot lgz partz) ]
(recur nxxt))
(if-let [[oldpivot & rightpartz] partz]
(cons oldpivot (qsort-inner rightpartz))
[]))))))
(defn qsort [ xs ]
(qsort-inner (list xs)))
该算法由对 的调用开始qsort，它将传递的数字列表封装到另一个列表中（从而创建一个包含单个列表的列表），然后调用qsort-inner.
(qsort [10 4 5 88 7 1]) ;; (qsort-inner [[10 4 5 88 7 1]])
;; (1 4 5 7 10 88)
qsort-inner有三个值得注意的点：
- 它延迟了实际处理。它不是返回对输入列表进行完整排序的结果，而是返回一个“lazy-seq”，它是一个 (object? thing? thunk ?) 在查询时发出排序序列的下一个数字，即在一个根据需要。计算的状态由悬挂的尾部给出
(cons oldpivot (qsort-inner rightpartz)) - 每当算法沿着排序树“向左”游荡时，都会使用 + 尾递归部分（有关算法的详细信息，请参见下文。
loop）recur (qsort-inner rightpartz)当获得下一个最小数字并且可以“重新排列”排序树时使用完全递归调用（有关算法详细信息，请参见下文。）
借助这个lazy-seq东西，我们可以让算法一一发出数据：
;; the full result is generated on printout
(qsort [10 4 5 88 7 1])
(1 4 5 7 10 88)
;; store the lazy-seq and query it
(def l (qsort [10 4 5 88 7 1]))
(first l)
;; 1
(second l)
;; 4
我正在考虑如何在 Prolog 中执行这种惰性快速排序。事实上，懒惰，至少在这种情况下，在 Prolog 中是通过回溯免费提供的！我们可以要求第一个结果，计算停止，然后通过回溯获得下一个结果。
qsort_inner(X, [[],X|_]).
qsort_inner(X, [[],_|WorkRest]) :- qsort_inner(X, WorkRest).
qsort_inner(X, [[Piv|Ns]|WorkRest]) :-
pick_smaller(Piv,Ns,SMs),
pick_notsmaller(Piv,Ns,NSMs),
qsort_inner(X,[SMs,Piv,NSMs|WorkRest]).
pick_smaller(Pivot,Ins,Outs) :- include(@>(Pivot),Ins,Outs).
pick_notsmaller(Pivot,Ins,Outs) :- exclude(@>(Pivot),Ins,Outs).
qsort(X,Lin) :- qsort_inner(X,[Lin]).
“懒惰”地对列表进行排序：
qsort(X,[3,2,1]).
X = 1;
X = 2;
X = 3;
false
必须得到他们所有：
qsort_fully(Lin,Lout) :- bagof(X, qsort(X, Lin), Lout).
不幸的是，跟踪计算状态的数据结构并不明显：它在堆栈上，不能统一为变量。因此，当我在 Prolog 的顶层时，只能使用这种“懒惰”。
如何捕获计算状态并稍后调用它？
注意快速排序的工作原理
- 给定一个数字列表，该算法选择列表的第一个元素作为枢轴值（图像中的浅绿色）。
- 然后，它构建一棵树，其中那些数字严格小于“左侧”列表中的枢轴值，枢轴本身（深绿色）和那些大于或等于“右侧”列表中的枢轴值的数字。
- 然后它递归地沿着这棵树“向左”移动。
- 这一直持续到小于枢轴值的数字列表为空。
- 此时，枢轴值（此处为 28）是最小的数字，可以输出。
- 这使得列表对一个元素进行排序更小。现在可以通过简单的重新排列操作将树减少一级：现在无左分支和无枢轴的“最深的树节点，但一个”的右分支成为树节点的左分支“最深的树 -节点但两个”。
- 现在可以再次“向左”搜索最小元素。
树结构不需要明确保留，因为它不包含任何信息。相反，交替的“叶子列表”和“枢轴编号”的序列保存在一个列表中。这就是为什么我们最初的“数字列表”。
