<p>std::nth_element 是计算百分位数最高效的方式，平均时间复杂度 O(n)，通过 k = round(p/100 * (n-1)) 定位后直接获取第 k 小元素；需注意索引范围、副本使用及 n=0/1 边界处理。</p>
用 std::nth_element 手动实现百分位数计算
标准库没有直接叫 percentile 的函数，但 std::nth_element 是最轻量、最常用的方式——它能在平均 O(n) 时间内找到第 k 小的元素，正好对应百分位数的位置。
关键点：百分位数不是“排序后取某索引”，而是“值使得至少 p% 的数据 ≤ 它”。常见定义（如 NumPy 的 linear 插值）在 C++ 中需手动处理边界和插值，但多数业务场景（如性能监控阈值、日志延迟 P95）只需近似值，std::nth_element 足够且更快。
- 先算目标位置：
size_t k = static_cast<size_t>(std::round((p / 100.0) * (n - 1)));</size_t>（注意是n-1，因 0-based 索引下 P0 是最小值、P100 是最大值） - 确保
k在[0, n-1]范围内，否则截断 - 调用
std::nth_element(vec.begin(), vec.begin() + k, vec.end());，之后vec[k]就是第k小的值 - 若需原数组不变，务必传入副本；
std::nth_element会部分重排原容器
用 std::sort + 线性插值支持更精确的百分位定义
当必须匹配 Python NumPy 或 R 的 linear 插值规则时（例如 P95 应落在两个相邻元素之间），就得先完整排序，再按公式计算。
公式为：value = low + (high - low) * (fractional_index - floor(fractional_index))，其中 fractional_index = (p/100) * (n-1)。
立即学习“C++免费学习笔记（深入）”；
-
std::sort时间复杂度O(n log n)，比nth_element慢，但换来确定性顺序和插值能力 - 注意
n == 0或n == 1的边界：前者返回NaN或抛异常，后者直接返回唯一元素 - 插值时索引可能落在
[0, n-1]外（如p=0时fractional_index=0，p=100时等于n-1），此时不插值，直接取端点 - 示例：对
{1, 3, 5, 7}（n=4）求 P90 →fractional_index = 0.9 * 3 = 2.7→ 取arr[2]=5和arr[3]=7插值 →5 + (7-5)*0.7 = 6.4
避免 std::partial_sort 的常见误用
有人想用 std::partial_sort 提前拿到前 k 个最小值再取最大，这看似合理，但实际是过度操作——它时间复杂度接近 O(n log k)，比 std::nth_element 差，且仍会修改原序列前 k 个位置的顺序。
-
std::partial_sort适合“找前 K 小并保持它们有序”，而百分位只要一个值，不需要有序子集 - 若误写成
partial_sort(..., ..., begin()+k+1)，容易越界（k+1 > size()），触发未定义行为 - 调试时发现结果偶尔偏大或偏小，大概率是用了
partial_sort却没意识到它只保证前k个有序，第k个未必是全局第k小（它可能是前k里的最大者，但不等于整体第k小）
整型数组要注意浮点精度与溢出
百分位计算本质是浮点运算，即使输入是 int，中间索引也得用 double 算，否则 (p * (n-1)) / 100 整除会丢精度（如 p=95, n=20 → 95*19=1805 / 100 = 18，正确；但 p=99, n=100 → 99*99=9801 / 100 = 98，实际应为 98.01，影响插值）。
- 始终用
double做百分位索引计算，再转size_t或用于插值 - 大数组（
n > 1e7）用std::nth_element时，注意某些 STL 实现（如 libstdc++）在n极大时退化到O(n log n)，可考虑pdqsort替代 - 若数组含
NaN或INF（如double类型），std::nth_element行为未定义，需预先过滤
实际写的时候，90% 的场景用 std::nth_element 加简单截断就够了；真要严格对齐其他语言的插值结果，才值得上 std::sort 和手工插值。最易被忽略的是索引公式的分母——用 n 还是 n-1，差一点，P99 就可能错一个数量级。
