clojure - 多个有序数组的快速排序算法

Question

我有 4 个数组，它们是有序的。我希望能够将它们组合成一个单一的排序数据结构，然后懒惰地从中获取。
有没有一种有效的方法来做到这一点？

[1 3 4 6 9 10 15]
[2 3 6 7 8 9 10]
[1 3 6 7 8 9 10]
[1 2 3 4 8 9 10]

=> [1 1 1 2 2 3 3 3 3 4]

Answer 1

Clojure 带有一个生成或操作惰性序列的函数库，例如 map , iterate和 take-while .我相信合并算法可以通过组合它们来表达，就像这样。

(defn insert-into-sorted [dst x]
  (let [x0 (first x)
        a (take-while #(< (first %) x0) dst)
        b (drop (count a) dst)]
    (vec (concat a [x] b))))

(defn next-arrays [arrs]
  (let [[f & r] arrs
        restf (rest f)]
    (if (empty? restf)
      r
      (insert-into-sorted r restf))))

(defn merge-sorted-arrays [arrs]
  (->> arrs
       (filter seq)
       (sort-by first)
       (iterate next-arrays)
       (take-while seq)
       (map ffirst)))

我们可以这样称呼它:

(merge-sorted-arrays [[1 3 4 6 9 10 15]
                      [2 3 6 7 8 9 10]
                      [1 3 6 7 8 9 10]
                      [1 2 3 4 8 9 10]])
;; => (1 1 1 2 2 3 3 3 3 4 4 6 6 6 7 7 8 8 8 9 9 9 9 10 10 10 10 15)

确实，您可以执行类似 (sort (apply concat ...)) 的操作。但如果您有大量数据，这可能会导致效率低下。
更新 :此代码的先前版本包含对 count 的调用这限制了它对合并有限长度序列的适用性。通过将其更改为使用 empty?相反，没有这样的限制，我们现在可以使用它来合并无限长度的序列:

(take 12 (merge-sorted-arrays [(iterate (partial + 1.1) 1) (iterate (partial + 1.11) 1)]))
;; => (1 1 2.1 2.1100000000000003 3.2 3.2200000000000006 4.300000000000001 4.330000000000001 5.4 5.440000000000001 6.5 6.550000000000002)