快速排序

看了《The Joy of Clojure》的快速排序，觉得比较丑，而且不通用。所以自己又写了一个。不过有一个比不上书里面的。书里面的支持 lazy-seq，而下面这个不支持。可能正是因为要支持 lazy-seq 所以书里面的那个才会那么繁琐吧……

(defn- split-by [pred coll]
  [(filter pred coll) (remove pred coll)])

(defn qsort-by [comparator work]
  (letfn [(step [ret [pivot & rst :as work]]
            (if-not work
              ret
              (let [[left right] (split-by #(< (comparator % pivot) 0) rst)]
                (if (seq left)
                  (recur ret (concat left [pivot] right))
                  (recur (conj ret pivot) rst)))))]
    (seq (step [] (seq work)))))

(println (qsort-by - [57 66 72 27 16]))
(println (qsort-by - []))
(println (qsort-by - nil))

;=> (16 27 57 66 72)
;=> nil
;=> nil

快速排序（升序）我理解为：给定一个轴（pivot)，遍历所有还没有排序完整的元素（rst），把小于轴的元素放到轴的左边（left），把不小于轴的元素放到轴的右边（right）。完全排序好的元素放到结果集（ret）里。如果左边有元素，说明找到了比轴还要小的元素。那么结果集不动，因为还没有找到最小的元素。如果左边没有元素，说明当前的轴就是最小的，把它加入结果集。

split-by 不同于 split-with。split-with 在遇到第一个不满足条件的元素后就终止了。而 split-by 会把整个集合都遍历一遍（这里的实现是遍历了两遍）。

如果需要排序，请用 Clojure 核心库的 sort 函数。这个函数转调 java.util.Arrays.sort 函数，它是经过高度优化的。我的测试表明我的函数比标准库的慢了两三个数量级…… -_-!