数据流中的中位数

传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可，但是因为数组在不断增长， 每增长一位便排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化，这个过程就让我们想到了插入排序：遍历后续数组每个元素时将它插入前面排好序的部分的相应位置。

step 1：用一数组存储输入的数据流。 step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。 step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。

 private ArrayList<Integer> list=new ArrayList<Integer>();
    public void Insert(Integer num) {
        if(list.isEmpty()){
            list.add(num);
        }else {
            int i=0;
            for(;i<list.size();i++){
                if(num>=list.get(i)) break;
            }
            list.add(i,num);
        }
    }

    public Double GetMedian() {
        int l=list.size();
        if(l%2==1){
            return (double)list.get(l/2);
        }else {
            double a=(double) list.get(l/2);
            double b=(double) list.get(l/2-1);
            return (a+b)/2;
        }
    }