如何在超大规模的无序数据中求中位数？

核心回答

先确认数据类型、可用内存、能否修改或多遍扫描，以及要精确还是近似中位数。对于1200万条这类规模，数据多并不自动意味着放不进内存。空数据则没有中位数。能装入内存时可用快速选择，期望O(n)；不能装下时，考虑按值域计数分桶或外部排序，而不是直接上两个占O(n)空间的堆。

按常见数值定义，奇数n取排序后中间值；偶数取第n/2与n/2+1个值的平均，这里名次从1开始。若业务要求下中位数或上中位数，需先约定。

情况一：能放入内存

快速选择选择pivot，把数据分成小于、等于和大于它的部分，根据目标名次只继续处理一侧；重复值多时三路划分可直接覆盖一整段名次。随机pivot通常给出期望O(n)，最坏O(n²)，严格最坏线性需要更强的选主元策略。

偶数需要两个中央顺序统计量，可以共同选择或分别定位，不能只找到其中一个。若不能修改原数组，复制的额外空间也应计入。

例如1200万个32位整数的裸数据约48MB；64位则约96MB。若用Python对象列表，还有指针、对象与容器开销，不能拿裸整数大小当进程内存。先做容量估计，再决定是否需要外存方案。

情况二：内存放不下，但允许多遍扫描

若整数值域小，直接统计每个值出现次数，再累计到中央名次，空间O(值域大小)。

值域较大时，可按数值区间分桶并计数，确定目标所在的桶，再扫描原数据只保留该桶，或继续细分。若此前桶共有c条，原目标是第k小，则桶内目标为第k−c小。偶数的两个目标可能落在不同桶，必须分别定位。

关键是按有序值域分桶，随机哈希分桶不能根据桶号判断大小。分布极度偏斜时不能假设每桶均匀；每轮需确认有效缩小范围，处理重复值、边界和落在同一值上的大量记录。其代价主要是多轮扫描与I/O。

通用外存方案

将数据分成可放入内存的块，各自排序写成有序段，再做多路归并，累计到所需中央名次即可停止。内存中只保留各段缓冲和归并堆，但会产生临时文件及读写成本；归并路数受缓冲、文件句柄和存储限制。

若数据只来一遍且需要持续返回精确中位数，可用最大堆/最小堆维护两半，单次插入O(log n)、查询O(1)，但总空间仍是O(n)。严格内存受限时，要改变存储假设或接受有误差保证的近似分位数方法，不能把两个堆称为常数空间方案。

参考资料