#Edit：正如@Hunaphu 所指出的（以及@whuber 在他的回答中），我给OP 的原始答案（如下）是错误的。首先对初始批次进行排序然后继续向上或向下更新中位数确实更快（取决于新数据点是落在当前中位数的左侧还是右侧）。

对数组进行排序以计算中位数是不好的形式。中位数（和其他分位数）通常使用快速选择算法计算，复杂度$O(n)$

您可能还想在此处查看我对最近相关问题的回答。

如果您愿意容忍近似值，还有其他方法。例如，一个近似值是一个值，其等级在距真实中位数的某个（用户指定的）距离内。例如，中位数的（归一化）等级为 0.5，如果您指定 10% 的误差项，您会想要一个等级在 0.45 和 0.55 之间的答案。

如果这样的答案是合适的，那么有许多解决方案可以用于滑动数据窗口。基本思想是维护一定大小的数据样本（大约 1/误差项）并计算该样本的中位数。可以证明，无论输入的性质如何，得到的中位数都很有可能满足我上面提到的属性。

因此，主要问题是如何维护一定大小的数据的运行样本，并且有很多方法可以解决这个问题，包括称为储层采样的技术。比如这篇论文：http ://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

这是一篇描述一种可能算法的文章。包含源代码和一个相当严肃的应用程序（基于激光干涉的引力波检测），因此您可以期待它经过良好测试。

如果您将一个长度为 k 的数据窗口维护为一个排序的双向链表，那么，通过二分搜索（在每个新元素移动到窗口中时插入它）和一个循环指针数组（立即定位需要删除），窗口的每次移动需要 O(log(k)) 的努力来插入一个元素，只需 O(1) 的努力来删除移出窗口的元素，并且只需 O(1) 的努力来找到中位数（因为每次在列表中插入或删除一个元素时，您都可以在 O(1) 时间内更新指向中位数的指针）。因此，处理长度为 N 的数组的总工作量为 O((nk)log(k)) <= O(n log(k))。这比迄今为止提出的任何其他方法都要好，而且它不是近似值，而是精确的。