轉(zhuǎn)自程序員編程藝術(shù)，topk實現(xiàn)算法

尋找最大的k個數(shù)的問題的實用范圍更廣，因為它牽扯到了一個Top K算法問題，以及有關(guān)搜索引擎，海量數(shù)據(jù)處理等廣泛的問題。

0、咱們先簡單的理解，要求一個序列中最小的k個數(shù)，按照慣有的思維方式，很簡單，先對這個序列從小到大排序，然后輸出前面的最小的k個數(shù)即可。

1、至于選取什么的排序方法，我想你可能會第一時間想到快速排序，我們知道，快速排序平均所費時間為n*logn，然后再遍歷序列中前k個元素輸出，即可，總的時間復(fù)雜度為O（n*logn+k）=O（n*logn）。

2、咱們再進(jìn)一步想想，題目并沒有要求要查找的k個數(shù)，甚至后n-k個數(shù)是有序的，既然如此，咱們又何必對所有的n個數(shù)都進(jìn)行排序列?

這時，咱們想到了用選擇或交換排序，即遍歷n個數(shù)，先把最先遍歷到得k個數(shù)存入大小為k的數(shù)組之中，對這k個數(shù)，利用選擇或交換排序，找到k個數(shù)中的最大數(shù)kmax（kmax設(shè)為k個元素的數(shù)組中最大元素），用時O（k）（你應(yīng)該知道，插入或選擇排序查找操作需要O（k）的時間），后再繼續(xù)遍歷后n-k個數(shù)，x與kmax比較：如果xkmax，則不更新數(shù)組。這樣，每次更新或不更新數(shù)組的所用的時間為O（k）或O（0），整趟下來，總的時間復(fù)雜度平均下來為：n*O（k）=O（n*k）。

3、當(dāng)然，更好的辦法是維護(hù)k個元素的最大堆，原理與上述第2個方案一致，即用容量為k的最大堆存儲最先遍歷到的k個數(shù)，并假設(shè)它們即是最小的k個數(shù)，建堆費時O（k）后，有k1O（n*logk）。此方法得益于在堆中，查找等各項操作時間復(fù)雜度均為logk（不然，就如上述思路2所述：直接用數(shù)組也可以找出前k個小的元素，用時O（n*k））。

所以，綜合考慮，我們一般還是選擇用建立k個元素的最大堆的方法解決此類尋找最小的k個數(shù)的問題。