一般來說都是針對數(shù)據(jù)量特別大，內(nèi)存有限制的。

第一類：topk問題

比如，在海量數(shù)據(jù)中找前50大的數(shù)據(jù)怎么辦？

方法一：使用小頂堆，用小頂堆維護(hù)這50個元素，當(dāng)有新元素到來時，直接與堆頂進(jìn)行比較（小頂堆堆頂最小），如果比堆頂大，替換堆頂，調(diào)整堆結(jié)構(gòu)。

堆中含k個元素，堆內(nèi)部調(diào)整時間復(fù)雜度logk，一共n個數(shù)據(jù)，每來一個都要進(jìn)行一次堆調(diào)整，總的時間復(fù)雜度O(nlogk)，總的空間復(fù)雜度O(k)。

方法二：使用快排，快排的思想是找標(biāo)準(zhǔn)值，標(biāo)準(zhǔn)值左邊都是比它小的，右邊都是比它大的，返回中間標(biāo)準(zhǔn)值的位置，找前k大的，就在標(biāo)準(zhǔn)值的右邊進(jìn)行查找，步驟一樣（先確定標(biāo)準(zhǔn)值，將小于標(biāo)準(zhǔn)值的放入左側(cè)，大于標(biāo)準(zhǔn)值放入右側(cè)）

開始數(shù)據(jù)量為n，進(jìn)行一次二分?jǐn)?shù)據(jù)量變?yōu)閚/2，后續(xù)只需要在這n/2中進(jìn)行查找，進(jìn)行兩次變?yōu)閚/4以此類推...最終時間復(fù)雜度n+n/2+n/4+...+1=2n-1，總的時間復(fù)雜度O(n)。

方法二同樣適用無序元素中找第k大的數(shù)，時間復(fù)雜度要求O(n)

第二類：海量數(shù)據(jù)的兩個文件找相同

比如，兩個文件中存放1000萬電話號碼，找這兩個文件中相同的電話號碼？

位圖法，對于電話號一共11位，從10000000000~19999999999，大約10G空間，采用位圖法該電話號存在對應(yīng)為1，不存在對應(yīng)0，將存儲空間壓縮到10G/8=1.25G。

第三類：海量數(shù)據(jù)排序

比如有10GB的訂單數(shù)據(jù)。希望按照訂單的金額（金額是整數(shù)）進(jìn)行排序，但是內(nèi)存只有幾百M(fèi)B，無法一次性加載到內(nèi)存。

方法一：采用分桶排序。加入金額是0-10萬，分成100個桶，每個桶的范圍是1千。比如桶0是從0~1000，桶1是從1001~2000...數(shù)據(jù)按照區(qū)域進(jìn)行劃分。存在100個文件中，文件內(nèi)部進(jìn)行排序，可以使用快排，依次從桶0、桶1...中取元素，得到的就是有序的10GB數(shù)據(jù)。時間復(fù)雜度O(nlogn/100)，計算方法為：100個文件，每個文件進(jìn)行快排，每個文件數(shù)據(jù)n/100，100*(NlogN)，其中N為n/100，最終結(jié)果為O(nlogn/100)。

存在的問題是如果數(shù)據(jù)在某個范圍特別多，比如某個桶有1GB的數(shù)據(jù)，這種情況怎么辦?

對這個桶中元素再進(jìn)行分桶，各桶有序再合并。

方法二：將數(shù)據(jù)等分到100個文件中，每個文件相當(dāng)于100MB的數(shù)據(jù)，每個文件內(nèi)部快排。同時維護(hù)一個小頂堆。每次取堆頂，可以先放入緩存，最后放入文件中。

方法三：文件之間兩兩合并，相當(dāng)于合并有序列表。

既然找10億元素中的中位數(shù)，就是找第5億個、第5億+1個，每個桶有相應(yīng)的存儲元素個數(shù)，大致確定5億、5億+1元素具體位于哪個桶，再對該桶進(jìn)行分桶，桶的間距為1，再進(jìn)行查找即可。