思路一

　　這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到那個區(qū)域，同時(shí)知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計(jì)落在這個區(qū)域中的那些數(shù)就可以了。

　　實(shí)際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進(jìn)行統(tǒng)計(jì)了。

　　思路二

　　同樣需要做兩遍統(tǒng)計(jì)，如果數(shù)據(jù)存在硬盤上，就需要讀取2次。

　　方法同基數(shù)排序有些像，開一個大小為65536的Int數(shù)組，遍讀取，統(tǒng)計(jì)Int32的高16位的情況，也就是0-65535，都算作0,65536 - 131071都算作1。就相當(dāng)于用該數(shù)除以65536。Int32 除以 65536的結(jié)果不會超過65536種情況，因此開一個長度為65536的數(shù)組計(jì)數(shù)就可以。每讀取一個數(shù)，數(shù)組中對應(yīng)的計(jì)數(shù)+1，考慮有負(fù)數(shù)的情況，需要將結(jié)果加32768后，記錄在相應(yīng)的數(shù)組內(nèi)。

　　遍統(tǒng)計(jì)之后，遍歷數(shù)組，逐個累加統(tǒng)計(jì)，看中位數(shù)處于哪個區(qū)間，比如處于區(qū)間k，那么0- k-1的區(qū)間里數(shù)字的數(shù)量sum。