题目描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

分析：

插入排序。

代码：

1 class Solution { 2 public: 3     vector
     
       v; 4     int vSize = 0; 5     void Insert(int num) { 6         v.push_back(num); 7         for(int i = vSize - 1; i >= 0; i--) { 8             if(v[i] <= num) { 9                 v[i + 1] = num;10                 break;11             } else {12                 v[i + 1] = v[i];13                 if(i == 0) v[0] = num;14             }15         }16         vSize++;17     }18     double GetMedian() {19         if(vSize & 1) return v[vSize >> 1];20         else return (v[vSize >> 1] + v[(vSize >> 1) - 1]) / 2.0;21     }22 };