代码之家 › 专栏 › 技术社区 › R u c k s a c k

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

counting-sort clojure sorting

0

R u c k s a c k · 技术社区 · 8 年前

假设我有一个整数数组 xs 从中获取值 0 到 max ,我需要在O(n)时间内排序,所以我不能 (sort xs) .

有没有办法用 frequencies 作用

用另一种语言,我会 for 迭代整数的步骤 0 到 最大值 ,对于每个值 x 在该范围内,查找 (frequencies x) 然后做 repeat (frequencies x) x 或者别的什么。

至关重要的是,我需要按照从最小到最高的顺序来做这件事,这就是整个事情的排序。所以我不想 map 中的每个数字 xs型 .

有没有关于clojure式惯用解决方案的想法?

谢谢

2 回复 | 直到 8 年前

1

Lee 8 年前

更新向量并不完全是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)))))

2

1

cfrick 8 年前

你可以照你对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))))