像装箱程序之类的东西怎么样？假设（出于说明目的）您知道值在 1 到 100 万之间。设置 N 个大小为 S 的箱。因此，如果 S=10000，您将有 100 个箱，对应于值 [1:10000, 10001:20000, ... , 990001:1000000]

然后，逐步检查这些值。而不是存储每个值，只需在适当的 bin 中增加计数器。使用每个 bin 的中点作为估计值，您可以对中值做出合理的近似。您可以通过更改 bin 的大小将其缩放到所需的精细或粗糙分辨率。您仅受您拥有多少内存的限制。

由于您不知道您的值可能有多大，因此只需使用一些快速粗略计算来选择一个足够大的 bin 大小，以便您不太可能耗尽内存。您也可以稀疏地存储 bin，这样您只添加一个包含值的 bin。

编辑：

ryfm 提供的链接给出了一个这样做的例子，附加步骤是使用累积百分比来更准确地估计中值 bin 内的点，而不仅仅是使用中点。这是一个很好的改进。

我将您重定向到我对类似问题的回答。简而言之，它是一种读取一次的“即时”算法，具有最坏情况复杂度来计算（精确）中位数。$O(n)$

Rivest-Tarjan-Selection 算法（有时也称为中位数算法）将让您无需任何排序即可在线性时间计算中位数元素。对于大型数据集，这可能比对数线性排序快很多。但是，它不会解决您的内存存储问题。

您能否将数据集分组为更小的数据集（例如 100 或 1000 或 10,000 个数据点），然后计算每个组的中位数。如果您使用足够的数据集执行此操作，则可以绘制每个较小集的结果的平均值之类的东西，这将通过运行足够的较小数据集收敛到“平均”解决方案。