中位数是观察值低于 1/2 和高于 1/2 的点。同样，第 25 个百分位数是最小值和中位数之间的数据的中位数，第 75 个百分位数是中位数和最大值之间的中位数，所以是的，我认为你在应用你首先使用的任何中位数算法时都处于坚实的基础上将整个数据集分区它，然后对两个结果块进行分区。

更新：

这个关于 stackoverflow 的问题引出了这篇论文：Raj Jain，Imrich Chlamtac：在不存储观测值的情况下动态计算分位数和直方图的 P² 算法。交流。ACM 28(10): 1076-1085 (1985)其摘要表明您可能对它很感兴趣：

提出了一种启发式算法，用于动态计算中位数和其他分位数。在生成观测值时动态生成估计值。不存储观察结果；因此，无论观察次数如何，该算法的存储需求都非常小且固定。这使其非常适合在可用于工业控制器和记录器的分位数芯片中实现。该算法进一步扩展到直方图绘制。分析算法的准确性。

对您发布的方法进行了非常轻微的更改，您可以计算任意百分位数，而无需计算所有分位数。这是Python代码：

class RunningPercentile:
    def __init__(self, percentile=0.5, step=0.1):
        self.step = step
        self.step_up = 1.0 - percentile
        self.step_down = percentile
        self.x = None

    def push(self, observation):
        if self.x is None:
            self.x = observation
            return

        if self.x > observation:
            self.x -= self.step * self.step_up
        elif self.x < observation:
            self.x += self.step * self.step_down
        if abs(observation - self.x) < self.step:
            self.step /= 2.0

和一个例子：

import numpy as np
import matplotlib.pyplot as plt

distribution = np.random.normal
running_percentile = RunningPercentile(0.841)
observations = []
for _ in range(1000000):
    observation = distribution()
    running_percentile.push(observation)
    observations.append(observation)

plt.figure(figsize=(10, 3))
plt.hist(observations, bins=100)
plt.axvline(running_percentile.x, c='k')
plt.show()