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