clojure的慣用選擇排序

Question

我試圖在clojure中實現選擇排序O（n2）。是的，基礎排序使用非常高效的java數組排序。不過這是一個學習練習。

以下作品的代碼，但是我在想，如果有重寫它的更地道的方式，如下面似乎笨重 -

(defn mins [coll] 
    (reduce (fn[[min-coll rest-coll] val] 
      (case (compare val (first min-coll)) 
       -1 [[val] (apply conj rest-coll min-coll)] 
       0 [(conj min-coll val) rest-coll] 
       1 [min-coll (conj rest-coll val)])) 
      [[(first coll)] []] 
      (rest coll))) 

;; (mins [3 1 1 2]) => [[1 1] [3 2]] 

(defn selection-sort [coll] 
    (loop [[sorted coll] [[] coll]] 
    (let [[s c] (mins coll)] 
     (if-not (seq coll) 
     sorted 
     (recur [(concat sorted s) c]))))) 

(selection-sort [3 1 1 2 5 7 8 8 4 6]) 

Answer 1

您可以使用以下方法：

(defn remove-first [coll e] 
    (if-let [pos (and (seq coll) (.indexOf coll e))] 
     (vec (concat 
      (subvec coll 0 pos) 
      (subvec coll (inc pos)))) 
     coll)) 

(defn best [coll f] 
    (reduce f 
      (first coll) 
      (rest coll))) 

(defn select-sort 
    ([coll] (select-sort coll min)) 
    ([coll fmin] 
    (loop [sorted (transient []) c (vec coll)] 
    (if (seq c) 
     (let [n (best c fmin)] 
     (recur (conj! sorted n) (remove-first c n))) 
     (persistent! sorted))))) 

=> (select-sort [3 5 2]) 
=> [2 3 5] 

=> (select-sort [3 5 2] max) 
=> [5 3 2] 

Answer 2

功能的解決方案可能是：

(defn selection-sort 
    [input] 
    (let [ixs (vec (range (count input))) 
     min-key-from (fn [acc ix] (apply min-key acc (subvec ixs ix))) 
     swap (fn [coll i j] (assoc coll i (coll j) j (coll i)))] 
    (reduce 
    (fn [acc ix] (swap acc ix (min-key-from acc ix))) input ixs)))