剑指offer系列之六十二：数据流中的中位数

题目描述

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

根据题目的意思，就是对数据流中的数据进行排序然后得到其中位数。要解决的关键问题是如何在读入数据的时候就对数据进行排序。实际上可以看成是插入排序算法的应用，可以维持一个list集合，保证每次读入数据集合中的数据都是排序的。基本思路是：从集合的第一个元素开始，依次比较与新读入的元素的大小关系，从而把新读入的数据插入到合适的位置。可以看出，这实际上就是插入排序的思想了。下面是具体实现的代码（已被牛客ac）：