algorithm - 获取序列中 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

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