思路一
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
思路二
同樣需要做兩遍統計，如果數據存在硬盤上，就需要讀取2次。
方法同基數排序有些像，開一個大小為65536的Int數組，遍讀取，統計Int32的高16位的情況，也就是0-65535，都算作0,65536 - 131071都算作1。就相當于用該數除以65536。Int32 除以 65536的結果不會超過65536種情況，因此開一個長度為65536的數組計數就可以。每讀取一個數，數組中對應的計數+1，考慮有負數的情況，需要將結果加32768后，記錄在相應的數組內。
遍統計之后，遍歷數組，逐個累加統計，看中位數處于哪個區間，比如處于區間k，那么0- k-1的區間里數字的數量sum。
京公網安備 11010802030320號