Clojure - sort函数

Question

我正在尝试编写一个递归排序函数，从低到高(duh)对列表进行排序。我目前得到的是输出，只是不是正确的输出。下面是我的代码：

(defn sort/predicate [pred loi]
   (if (empty? loi)
     ()
     (if (= (count loi) 1)
       (cons (first loi) (sort pred (rest loi)))
       (if (pred (first loi) (first (rest loi)))
         (cons (first loi) (sort pred (rest loi)))
         (if (pred (first (rest loi)) (first loi))
           (cons (first (rest loi)) (sort pred (cons (first loi) (rest (rest loi)))))
           (cons (first loi) (sort pred (rest loi))))))))

基本上，我比较列表中的前两个元素，如果第一个元素较小，则将其与列表中接下来的两个元素进行比较。如果列表的第二个元素较小，我会将第二个元素与第一个元素的cons的前两个元素以及第二个元素之后的所有内容排序的结果进行比较(很抱歉这很难理解)。然后，当列表中只剩下一个元素时，我将它抛到末尾并返回它。然而，在此过程中有一个bug，因为我应该得到以下内容：

>(sort/predicate < '(8 2 5 2 3))
(2 2 3 5 8)

但我得到的却是：

>(sort/predicate < '(8 2 5 2 3))
(2 5 2 3 8)

我是clojure的新手，所以非常感谢您的帮助。另外，我希望我的代码保持大致相同(我不想使用已经存在的排序函数)。谢谢

Answer 1

我不认为这是一种非常有效的排序方式，但我试图保持与您的意图一致：

(defn my-sort [cmp-fn [x & xs]]
  (cond
    (nil? x) '()
    (empty? xs) (list x)
    :else (let [[y & ys :as s] (my-sort cmp-fn xs)]
            (if (cmp-fn x y)
              (cons x s)
              (cons y (my-sort cmp-fn (cons x ys)))))))

Answer 2

；合并排序实现-不使用堆栈的递归排序

(defn merge-sort
  ([v comp-fn]
   (if (< (count v) 2) v
     (let [[left right] (split-at (quot (count v) 2) v)]
       (loop [result       []
              sorted-left  (merge-sort left comp-fn)
              sorted-right (merge-sort right comp-fn)]
         (cond
           (empty? sorted-left) (into result sorted-right)
           (empty? sorted-right) (into result sorted-left)
           :else (if (comp-fn 0 (compare (first sorted-left) (first sorted-right)))
                   (recur (conj result (first sorted-left)) (rest sorted-left) sorted-right)
                   (recur (conj  result (first sorted-right))  sorted-left (rest sorted-right))))))))
  ([v] (merge-sort v >)))

Answer 3

用Java实现的clojure.core/sort比较通用。

user=> (sort '(8 2 5 2 3))
(2 2 3 5 8)
user=> (sort > '(8 2 5 2 3))
(8 5 3 2 2)
user=> (source sort)
(defn sort
  "Returns a sorted sequence of the items in coll. If no comparator is
  supplied, uses compare.  comparator must implement
  java.util.Comparator.  If coll is a Java array, it will be modified.
  To avoid this, sort a copy of the array."
  {:added "1.0"
   :static true}
  ([coll]
   (sort compare coll))
  ([^java.util.Comparator comp coll]
   (if (seq coll)
     (let [a (to-array coll)]
       (. java.util.Arrays (sort a comp))
       (seq a))
     ())))
nil
user=>