如何在Clojure中实施整数的计数排序

Question

说我有一个整数 xs CC_1从 0到 max，我需要在o(n(时间中对其进行排序，所以我不能只做 (sort xs)。p>有没有办法使用frequencies函数？

在另一种语言中，我将进行for，以迭代从0到max的整数，对于该范围内的每个值x，查找(frequencies x)，然后进行repeat (frequencies x) x或其他内容。

>

至关重要的是，我需要按最小到最高的顺序进行操作，这就是使整个事情成为一种。因此，我不想仅在xs中的每个数字。

中

对clojure-ish惯用解决方案的任何想法？

谢谢。

Answer 1

更新向量不是很o(1(，但是您可以使用它来创建每个元素的计数：

(defn counting-sort [s]
  (if (empty? s)
    s
    (let [counts (reduce (fn [v e]
                           (update v e inc))
                         (vec (repeat (inc (apply max s)) 0))
                         s)]
      (apply concat (map-indexed #(repeat %2 %1) counts)))))

Answer 2

好吧，您可以用clojure做你说的事情：

(let [xs [1 2 1 4 1 5 1 8 7 7 7]
      fs (frequencies xs)
      max 10]
  (into [] 
    cat
    (for [i (range max) :when (contains? fs i)]
      (repeat (get fs i) i))))