劍指offer系列之六十二：資料流中的中位數

題目描述

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。

根據題目的意思，就是對資料流中的資料進行排序然後得到其中位數。要解決的關鍵問題是如何在讀入資料的時候就對資料進行排序。實際上可以看成是插入排序算法的應用，可以維持一個list集合，保證每次讀入資料集合中的資料都是排序的。基本思路是：從集合的第一個元素開始，依次比較與新讀入的元素的大小關系，進而把新讀入的資料插入到合适的位置。可以看出，這實際上就是插入排序的思想了。下面是具體實作的代碼（已被牛客ac）：