引用:CSDN算法之美
海量數(shù)據(jù)
一年的全國(guó)高考考生人數(shù)為500 萬，分?jǐn)?shù)使用標(biāo)準(zhǔn)分，最低100 ，最高900 ，沒有小數(shù)，要求對(duì)這500 萬元素的數(shù)組進(jìn)行排序。
分析：對(duì)500W數(shù)據(jù)排序，如果基于比較的先進(jìn)排序，平均比較次數(shù)為O(5000000*log5000000)≈1.112億。但是我們發(fā)現(xiàn)，這些數(shù)據(jù)都有特殊的條件： 100=<score<=900。那么我們就可以考慮桶排序這樣一個(gè)“投機(jī)取巧”的辦法、讓其在毫秒級(jí)別就完成500萬排序。
方法：創(chuàng)建801(900-100)個(gè)桶。將每個(gè)考生的分?jǐn)?shù)丟進(jìn)f(score)=score-100的桶中。這個(gè)過程從頭到尾遍歷一遍數(shù)據(jù)只需要500W次。然后根據(jù)桶號(hào)大小依次將桶中數(shù)值輸出，即可以得到一個(gè)有序的序列。而且可以很容易的得到100分有人，501分有人。
實(shí)際上，桶排序?qū)?shù)據(jù)的條件有特殊要求，如果上面的分?jǐn)?shù)不是從100-900，而是從0-2億，那么分配2億個(gè)桶顯然是不可能的。所以桶排序有其局限性，適合元素值集合并不大的情況。
典型
在一個(gè)文件中有10G個(gè)整數(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í)，中位數(shù)=(N+1)/2 ; 當(dāng)樣本數(shù)為偶數(shù)時(shí)，中位數(shù)為N/2與1+N/2的均值（那么10G個(gè)數(shù)的中位數(shù)，就第5G大的數(shù)與第5G+1大的數(shù)的均值了）。
分析：既然要找中位數(shù)，很簡(jiǎn)單就是排序的想法。那么基于字節(jié)的桶排序是一個(gè)可行的方法。
思想：將整型的每1byte作為一個(gè)關(guān)鍵字，也就是說一個(gè)整形可以拆成4個(gè)keys，而且最高位的keys越大，整數(shù)越大。如果高位keys相同，則比較次高位的keys。整個(gè)比較過程類似于字符串的字典序。
第一步:把10G整數(shù)每2G讀入一次內(nèi)存，然后一次遍歷這536,870,912即（102410241024）*2 /4個(gè)數(shù)據(jù)。每個(gè)數(shù)據(jù)用位運(yùn)算">>"取出最高8位(31-24)。這8bits(0-255)最多表示256個(gè)桶，那么可以根據(jù)8bit的值來確定丟入第幾個(gè)桶。最后把每個(gè)桶寫入一個(gè)磁盤文件中，同時(shí)在內(nèi)存中統(tǒng)計(jì)每個(gè)桶內(nèi)數(shù)據(jù)的數(shù)量NUM[256]。
代價(jià)：
(1) 10G數(shù)據(jù)依次讀入內(nèi)存的IO代價(jià)(這個(gè)是無法避免的，CPU不能直接在磁盤上運(yùn)算)。
(2)在內(nèi)存中遍歷536,870,912個(gè)數(shù)據(jù)，這是一個(gè)O(n)的線性時(shí)間復(fù)雜度。
(3)把256個(gè)桶寫回到256個(gè)磁盤文件空間中，這個(gè)代價(jià)是額外的，也就是多付出一倍的10G數(shù)據(jù)轉(zhuǎn)移的時(shí)間。
第二步：根據(jù)內(nèi)存中256個(gè)桶內(nèi)的數(shù)量NUM[256]，計(jì)算中位數(shù)在第幾個(gè)桶中。很顯然，2,684,354,560個(gè)數(shù)中位數(shù)是第1,342,177,280個(gè)。假設(shè)前127個(gè)桶的數(shù)據(jù)量相加，發(fā)現(xiàn)少于1,342,177,280，把第128個(gè)桶數(shù)據(jù)量加上，大于1,342,177,280。說明，中位數(shù)必在磁盤的第128個(gè)桶中。而且在這個(gè)桶的第1,342,177,280-N(0-127)個(gè)數(shù)位上。N(0-127)表示前127個(gè)桶的數(shù)據(jù)量之和。然后把第128個(gè)文件中的整數(shù)讀入內(nèi)存。(若數(shù)據(jù)大致是均勻分布的，每個(gè)文件的大小估計(jì)在10G/256=40M左右，當(dāng)然也不一定，但是超過2G的可能性很小)。注意，變態(tài)的情況下，這個(gè)需要讀入的第128號(hào)文件仍然大于2G，那么整個(gè)讀入仍然可以按照第一步分批來進(jìn)行讀取。
代價(jià)：
(1)循環(huán)計(jì)算255個(gè)桶中的數(shù)據(jù)量累加，需要O(M)的代價(jià)，其中m<255。
(2)讀入一個(gè)大概80M左右文件大小的IO代價(jià)。
第三步：繼續(xù)以內(nèi)存中的某個(gè)桶內(nèi)整數(shù)的次高8bit（他們的最高8bit是一樣的）進(jìn)行桶排序(23-16)。過程和第一步相同，也是256個(gè)桶。
第四步：一直下去，直到最低字節(jié)(7-0bit)的桶排序結(jié)束。我相信這個(gè)時(shí)候完全可以在內(nèi)存中使用一次快排就可以了。
整個(gè)過程的時(shí)間復(fù)雜度在O(n)的線性級(jí)別上(沒有任何循環(huán)嵌套)。但主要時(shí)間消耗在第一步的第二次內(nèi)存-磁盤數(shù)據(jù)交換上，即10G數(shù)據(jù)分255個(gè)文件寫回磁盤上。一般而言，如果第二步過后，內(nèi)存可以容納下存在中位數(shù)的某一個(gè)文件的話，直接快排就可以了（修改者注：我想，繼續(xù)桶排序但不寫回磁盤，效率會(huì)更高？）。
