获得序列中n个最小的数字

Question

从序列中取出n个最小数字的最有效方法是什么

[ [1 2 3] [9 2 1] [2 3 4] [5 6 7] ]

我想根据第一项从序列中取2个最小值,

[1 2 3] [2 3 4]

目前我正在整理整个列表,然后采取前n项,但这可能不是最有效的方法,这是一个很大的列表,我需要经常这样做.

Answer 1

Clojure 的乐趣，第 6.4 章描述了一种惰性排序算法。惰性排序的美妙之处在于，它只会执行查找前 x 值所需的工作。因此，如果 x << n，则该算法的复杂度为 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))