一、在一個(gè)文件中有 10G 個(gè)整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。
解決方案：桶排序。
1、讀入內(nèi)存2G數(shù)據(jù)，一個(gè)整數(shù)四個(gè)字節(jié)，將這四個(gè)字節(jié)取最高的一個(gè)字節(jié)即8位（用>>位移法取出）
2、一個(gè)字節(jié)共256種可能性，開辟256個(gè)文件，根據(jù)每個(gè)數(shù)的高8位寫入文件
3、重復(fù)上述算法直到所有數(shù)算完，同時(shí)記錄每個(gè)文件中的數(shù)的數(shù)量。
4、第一個(gè)文件數(shù)的個(gè)數(shù)+第二個(gè)文件數(shù)的個(gè)數(shù)... 可以判斷中位數(shù)在第幾個(gè)桶里面
5、把這個(gè)桶整個(gè)讀入內(nèi)存，之后如果大小小于2G就不用寫文件了，在內(nèi)存中計(jì)算就可以
6、這個(gè)桶里面的數(shù)高8位都一樣，用1中的方法去取第二高的字節(jié)并重復(fù)上面的算法，然后取第三高的字節(jié)重復(fù)算法，最后一個(gè)字節(jié)可以接著桶排序，也可以快排，就能得出中位數(shù)了
二、10億個(gè)整數(shù)，找出最大的1000個(gè)。
解決方案：有重復(fù)可以用分治法+快排或者小頂堆，如果沒有重復(fù)可以桶排
1、分治法+快排：將數(shù)分成內(nèi)存能裝的下的分?jǐn)?shù)，比如100份，每分進(jìn)行快排得到最大的1000個(gè)，然后將100*1000個(gè)數(shù)進(jìn)行快排取1000個(gè)。這里快排方法如下：每趟快排可以將數(shù)組分成數(shù)量不一定的兩部分，如果大的那份多余1000，再對著分進(jìn)行一次快排，如果再多再對多的那份快排一次，如果少了則對少的這份快排一次，如此循環(huán)直到夠1000個(gè)為止。
2、小頂堆：先從文件中讀取1000個(gè)數(shù)到內(nèi)存，建小頂堆，之后依次讀取，每讀一個(gè)數(shù)就和堆頂比較，小于堆頂則丟棄，大于堆頂則與堆頂交換再重建堆，直到全部讀取完畢。
3、桶排序：按最高位分256個(gè)桶，最高的一個(gè)應(yīng)該超過1000個(gè)數(shù)，再把這個(gè)桶拿出來按第二位繼續(xù)分桶，直到夠數(shù)了。