从序列中取n个最小数的最有效方法是什么，
[ [1 2 3] [9 2 1] [2 3 4] [5 6 7] ]
我想从基于第一项的序列中取2个最小值，
[1 2 3] [2 3 4]
目前我正在对整个列表进行排序，然后取前n项，但这可能不是最有效的方法，这是一个大列表，我需要经常这样做。
The Joy of Clojure, Chapter 6.4描述了一个lazy排序算法。惰性排序的美妙之处在于，它只会做尽可能多的工作来查找第一个x值。所以如果x <<这个算法是O(n)以下是该算法的修改版本。
(defn sort-parts
[work f]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [psmaller? (partial f pivot)]
(recur (list* (filter psmaller? xs)
pivot
(remove psmaller? xs)
parts)))
(when-let [[x & parts] parts]
(cons x
(sort-parts parts f)))))))
(defn qsort [xs f] (sort-parts (list xs) f))
(defn cmp [[a _ _] [b _ _]] (> a b))
(def a [[1 2 3] [9 2 1] [2 3 4] [5 6 7]])
(take 2 (qsort a cmp))
根据参考，您可以使用median-of-median算法在线性时间内选择第k个最小的元素，然后在线性时间内进行划分。这将为你提供O(n)中k个最小的元素。然而，元素是无序的，所以如果你想排序k个最小的元素，它将花费你另一个O(klogk)。
注意事项:
-
首先，虽然复杂度是O(n)，但不能保证小的常数，您可能会发现最小的改进，特别是当您的n相当小的时候。有一些随机线性选择算法可以在更好的实际时间内运行(通常在最坏的情况下预期运行时间为O(n)，但它们的常数比确定性的小)。
-
为什么不能以排序的方式维护数组?这可能会更高效。你只需要将每个元素插入到正确的位置，这需要花费O(logn)，但是找到最小的k将是O(1)(或O(k)，如果你必须重新构建数组)。
-
如果您决定不采用上述注意，那么另一种选择是在每个这样的过程之后保持数组排序，在0(1)到数组末尾提供插入，然后每次需要找到k个最小元素时执行"合并排序"。也就是说，你只对中的进行排序，然后在线性时间内合并它们。因此，这将花费O(mlogm + n)，其中m是自上次排序以来添加的元素数。
如果n很小，你可以创建第二个大小为n的列表，并对其进行排序，这样你就可以快速访问该列表中最大的列表;遍历大列表，检查每个元素是否都小于小列表中的最大值;如果是，将其插入到小列表中…小列表已经满了，把前面最老的去掉。
如果n小于3或4，你可以使用蛮力。如果n可以更大，你会想做一个二分查找来找到每个插入点。如果n可以非常大，那么可能需要一种不同的机制。