剑指Offer——数据流中的中位数

题目描述：

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

分析：

插入排序。

代码：

 1 class Solution {
 2 public:
 3     vector<int> 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 };