在一個文件中有10G個整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為2G。只寫出思路即可（內(nèi)存限制為2G意思是可以使用2G空間來運(yùn)行程序，而不考慮本機(jī)上其他軟件內(nèi)存占用情況。） 關(guān)于中位數(shù)：數(shù)據(jù)排序后，位置在最中間的數(shù)值。即將數(shù)據(jù)分成兩部分，一部分大于該數(shù)值，一部分小于該數(shù)值。中位數(shù)的位置：當(dāng)樣本數(shù)為奇數(shù)時，中位數(shù)=(N+1)/2 ; 當(dāng)樣本數(shù)為偶數(shù)時，中位數(shù)為N/2與1+N/2的均值（那么10G個數(shù)的中位數(shù)，就第5G大的數(shù)與第5G+1大的數(shù)的均值了）。

分析：既然要找中位數(shù)，很簡單就是排序的想法。那么基于字節(jié)的桶排序是一個可行的方法。

思想：將整型的每1byte作為一個關(guān)鍵字，也就是說一個整形可以拆成4個keys，而且最高位的keys越大，整數(shù)越大。如果高位keys相同，則比較次高位的keys。整個比較過程類似于字符串的字典序。

第一步:把10G整數(shù)每2G讀入一次內(nèi)存，然后一次遍歷這536,870,912即（1024*1024*1024）*2 /4個數(shù)據(jù)。每個數(shù)據(jù)用位運(yùn)算">>"取出最高8位(31-24)。這8bits(0-255)最多表示256個桶，那么可以根據(jù)8bit的值來確定丟入第幾個桶。最后把每個桶寫入一個磁盤文件中，同時在內(nèi)存中統(tǒng)計每個桶內(nèi)數(shù)據(jù)的數(shù)量NUM[256]。

代價：(1) 10G數(shù)據(jù)依次讀入內(nèi)存的IO代價(這個是無法避免的，CPU不能直接在 磁盤上運(yùn)算)。(2)在內(nèi)存中遍歷536,870,912個數(shù)據(jù)，這是一個O(n)的線性時間復(fù)雜度。(3)把256個桶寫回到256個磁盤文件空間中，這個代價是額外的，也就是多付出一倍的10G數(shù)據(jù)轉(zhuǎn)移的時間。

第二步：根據(jù)內(nèi)存中256個桶內(nèi)的數(shù)量NUM[256]，計算中位數(shù)在第幾個桶中。很顯然，2,684,354,560個數(shù)中位數(shù)是第1,342,177,280個。假設(shè)前127個桶的數(shù)據(jù)量相加，發(fā)現(xiàn)少于1,342,177,280，把第128個桶數(shù)據(jù)量加上，大于1,342,177,280。說明，中位數(shù)必在 磁盤的第128個桶中。而且在這個桶的第1,342,177,280-N(0-127)個數(shù)位上。N(0-127)表示前127個桶的數(shù)據(jù)量之和。然后把第128個文件中的整數(shù)讀入內(nèi)存。(若數(shù)據(jù)大致是均勻分布的，每個文件的大小估計在10G/256=40M左右，當(dāng)然也不一定，但是超過2G的可能性很小)。注意，變態(tài)的情況下，這個需要讀入的第128號文件仍然大于2G，那么整個讀入仍然可以按照第一步分批來進(jìn)行讀取。

代價：(1)循環(huán)計算255個桶中的數(shù)據(jù)量累加，需要O(M)的代價，其中m<255。(2)讀入一個大概80M左右文件大小的IO代價。

第三步：繼續(xù)以內(nèi)存中的某個桶內(nèi)整數(shù)的次高8bit（他們的最高8bit是一樣的）進(jìn)行桶排序(23-16)。過程和第一步相同，也是256個桶。

第四步：一直下去，直到最低字節(jié)(7-0bit)的桶排序結(jié)束。我相信這個時候完全可以在內(nèi)存中使用一次快排就可以了。

整個過程的 時間復(fù)雜在O(n)的線性級別上。但主要時間消耗在第一步的第二次內(nèi)存-磁盤數(shù)據(jù)交換上，即10G數(shù)據(jù)分255個文件寫回磁盤上。一般而言，如果第二步過后，內(nèi)存可以容納下存在中位數(shù)的某一個文件的話，直接快排就可以了。