是否可以/更快地从大型数组中计算分位数，而无需简单地排序然后索引

我有一个数组，包含10 000到50 000个元素，代表压力经济体中面临风险的值。我对使用普通权重计算此数组的第 x 个分位数感兴趣。

立即进入我的问题 - 是否可以在不先排序然后简单地索引的情况下确定大型未排序数组的分位数？或者也许在排序时实现功能以确定一些分位数？就我而言，速度是最重要的，但是不依赖于第一次排序的较慢方法对我来说也很有趣。

---

这样做的传统方法非常简单，首先对数组进行排序，然后构建SetWeights()进行一些简单的插值（Alpha是所需的分位数分数）

protected sealed override void SetWeights()
{
    double n = (NumberOfScenarios - 1) * Alpha + 1;
    if (Math.Abs(n - 1d) < double.Epsilon)
    {
        Weights = new List<double> { 1.0 };
        Indices = new List<int> { 0 };
    }
    else if (Math.Abs(n - NumberOfScenarios) < double.Epsilon)
    {
        Weights = new List<double> { 1.0 };
        Indices = new List<int> { NumberOfScenarios - 1 };
    }
    else
    {
        int k = (int)n;
        double d = n - k;
        Weights = new List<double> { 1.0 - d, d };
        Indices = new List<int> { k - 1, k };
    }
}

然后通过取权重的相应指数来计算分位数

public double Quantile(List<double> sortedScenarios)
{
    var varEstimator = 0.0;
    for (var i = 0; i < Indices.Count; ++i)
    {
        varEstimator += Weights[i] * sortedSequence[Indices[i]];
    }
    return varEstimator;
}