中位數(shù)即是排過序后的處于數(shù)組最中間的元素。 不考慮數(shù)組長度為偶數(shù)的情況。設(shè)集合元素個(gè)數(shù)為n。
簡單的想了下：
思路1） 把無序數(shù)組排好序，取出中間的元素
時(shí)間復(fù)雜度 采用普通的比較排序法 O(N*logN)
如果采用非比較的計(jì)數(shù)排序等方法， 時(shí)間復(fù)雜度 O(N), 空間復(fù)雜度也是O(N).
思路2） 
2.1）將前(n+1)/2個(gè)元素調(diào)整為一個(gè)小頂堆，
2.2）對后續(xù)的每一個(gè)元素，和堆頂比較，如果小于等于堆頂，丟棄之，取下一個(gè)元素。 如果大于堆頂，用該元素取代堆頂，調(diào)整堆，取下一元素。重復(fù)2.2步

2.3） 當(dāng)遍歷完所有元素之后，堆頂即是中位數(shù)。
思路3） 熟話說，想讓算法跑的更快，用分治！
快速排序之所以得名"快排",絕非浪得虛名！因?yàn)榭炫啪褪且环N分治排序法！
同樣，找中位數(shù)也可以用快排分治的思想。具體如下：
任意挑一個(gè)元素，以改元素為支點(diǎn)，劃分集合為兩部分，如果左側(cè)集合長度恰為 (n-1)/2，那么支點(diǎn)恰為中位數(shù)。如果左側(cè)長度<(n-1)/2, 那么中位點(diǎn)在右側(cè)，反之，中位數(shù)在左側(cè)。 進(jìn)入相應(yīng)的一側(cè)繼續(xù)尋找中位點(diǎn)。
這種方法很快，但是在最壞的情況下時(shí)間復(fù)雜度為O(N^2), 不過平均時(shí)間復(fù)雜度好像是O(N)。
思路4) 快排的方法存在不確定性,導(dǎo)致其最壞和最好的時(shí)候差別很大, 那么有沒有一種確定性的方法呢? 答案是有的
貌似算法導(dǎo)論里有講到. 這里我就先不深究了, 可以參考如下的文章, 
O(n)時(shí)間快速選擇

計(jì)算一下數(shù)組長度，除以2為整數(shù)的話，就取下標(biāo)為(長度/2)和（長度/2-1）的值相加除以2，不為整數(shù)就向下取整，取下標(biāo)為這個(gè)數(shù)的值