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

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

計算一下數組長度，除以2為整數的話，就取下標為(長度/2)和（長度/2-1）的值相加除以2，不為整數就向下取整，取下標為這個數的值