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

Question

假设我有一个整数数组 xs，取值从 0 到 max，我需要在 O(n) 时间内对它进行排序，所以我不能就做 (sort xs).

有没有办法用 frequencies 函数做到这一点？

在另一种语言中，我会做一个 for 来迭代从 0 到 max 的整数，对于该范围内的每个值 x，查找(frequencies x) 然后做 repeat (frequencies x) x 什么的。

至关重要的是，我需要按从小到大的顺序执行此操作，这就是使整个事情井然有序的原因。所以我不想 map xs 中的每个数字。

关于 clojure 风格的惯用解决方案有什么想法吗？

谢谢。

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))))

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

How to implement counting sort for integers in Clojure?

sorting

clojure

counting-sort