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

题目描述：

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

分析：

插入排序。

代码：

 class Solution {

 public:

     vector<int> v;

     int vSize = ;

     void Insert(int num) {

         v.push_back(num);

         for(int i = vSize - ; i >= ; i--) {

             if(v[i] <= num) {

                 v[i + ] = num;

                 break;

             } else {

                 v[i + ] = v[i];

                 if(i == ) v[] = num;

             }

         }

         vSize++;

     }

     double GetMedian() {

         if(vSize & ) return v[vSize >> ];

         else return (v[vSize >> ] + v[(vSize >> ) - ]) / 2.0;

     }

 };