場景
之前寫過一篇海量數(shù)據(jù)中統(tǒng)計ip出現(xiàn)次數(shù)最多的博客谈宛，今天再寫篇類似的户秤，當然會有不同的地方，相同的地方我快速寫過颠悬，詳細的可以看之前的博客矮燎。
今天要給100億個數(shù)字排序，100億個 int 型數(shù)字放在文件里面大概有 37.2GB赔癌，非常大诞外，內(nèi)存一次裝不下了。那么肯定是要拆分成小的文件一個一個來處理灾票，最終在合并成一個排好序的大文件峡谊。
實現(xiàn)思路
1.把這個37GB的大文件，用哈希分成1000個小文件，每個小文件平均38MB左右（理想情況）靖苇，把100億個數(shù)字對1000取模席噩，模出來的結(jié)果在0到999之間，每個結(jié)果對應(yīng)一個文件贤壁，所以我這里取的哈希函數(shù)是 h = x % 1000悼枢，哈希函數(shù)取得"好"，能使沖突減小脾拆，結(jié)果分布均勻馒索。
2.拆分完了之后，得到一些幾十MB的小文件名船，那么就可以放進內(nèi)存里排序了绰上，可以用快速排序，歸并排序渠驼，堆排序等等蜈块。
3.1000個小文件內(nèi)部排好序之后，就要把這些內(nèi)部有序的小文件迷扇，合并成一個大的文件百揭，可以用二叉堆來做1000路合并的操作，每個小文件是一路蜓席，合并后的大文件仍然有序器一。
- 首先遍歷1000個文件，每個文件里面取第一個數(shù)字厨内，組成 (數(shù)字, 文件號) 這樣的組合加入到堆里（假設(shè)是從小到大排序祈秕，用小頂堆），遍歷完后堆里有1000個 (數(shù)字雏胃，文件號) 這樣的元素
- 然后不斷從堆頂拿元素出來请毛，每拿出一個元素，把它的文件號讀取出來丑掺，然后去對應(yīng)的文件里获印，加一個元素進入堆述雾，直到那個文件被讀取完街州。拿出來的元素當然追加到最終結(jié)果的文件里。
- 按照上面的操作玻孟，直到堆被取空了唆缴，此時最終結(jié)果文件里的全部數(shù)字就是有序的了。
最后我用c++寫了個實驗程序黍翎，具體代碼在這里可以看到面徽。
思維拓展
類似的100億個數(shù)字求和，求中位數(shù)，求平均數(shù)趟紊，套路就是一樣的了氮双。
求和：統(tǒng)計每個小文件的和，返回給master再求和就可以了霎匈。
求平均數(shù)：上面能求和了戴差，再除以100億就是平均數(shù)了
求中位數(shù)：在排序的基礎(chǔ)上，遍歷到中間的那個數(shù)就是中位數(shù)了铛嘱。
更正暖释，評論中網(wǎng)友馬敬v，提出了不用對數(shù)字進行哈希墨吓，直接平均分成1000份球匕，進行內(nèi)部排序后，直接進行 k 路歸并排序帖烘，也是可以的亮曹。
