在較小的窗口大小上，n log n排序可能會起作用。有沒有更好的算法來實現這一點？
#Edit：正如@Hunaphu 所指出的（以及@whuber 在他的回答中），我給OP 的原始答案（如下）是錯誤的。首先對初始批次進行排序然後繼續向上或向下更新中位數確實更快（取決於新數據點是落在當前中位數的左側還是右側）。
對數組進行排序以計算中位數是不好的形式。中位數（和其他分位數）通常使用快速選擇算法計算，其中 $ O(n) $ 複雜。
您可能還想在此處查看我對最近相關問題的回答。
引用自：https://stats.stackexchange.com/questions/134