C++实现快速选择算法查找中位数 _ 均摊O(n)复杂度实现【源码】

高效定位中位数：为什么 std::nth_element 是你的首选工具

免费影视、动漫、音乐、游戏、小说资源长期稳定更新！ 👉 点此立即查看 👈

在C++编程中，高效查找序列的中位数是一个常见需求。std::nth_element 算法凭借其卓越的性能，成为解决此问题的首选方案。它基于快速选择算法实现，能够在均摊 O(n) 的时间复杂度内完成定位，远优于 std::sort 的 O(n log n)。其内部实现融合了三数取中、小数组插入排序优化及尾递归消除等工业级技巧，有效避免了最坏情况下的 O(n²) 性能退化。相比之下，std::partial_sort 在仅需单个中位数时也会进行不必要的额外排序，显得不够高效。

要正确使用 std::nth_element 计算中位数，需注意以下关键点：

• 对于奇数长度数组，中位数可直接定义为第 n/2 小的元素（基于0起始索引）。代码实现为：std::nth_element(v.begin(), v.begin() + v.size()/2, v.end())。
• 若需遵循严格的数学定义（偶数长度时取中间两数的平均值），则需分别定位第 (n-1)/2 和 n/2 小的两个元素。这里需避免一个常见误区：连续两次调用 std::nth_element 会破坏数组状态。更优的策略是调用一次定位其中一个元素，再通过一次线性扫描找到另一个。
• 必须确保输入容器支持随机访问迭代器（例如 std::vector、std::array），像 std::list 这类序列容器则不适用。

总而言之，std::nth_element 是C++中查找中位数的理想选择，它兼具算法效率、标准库的深度优化以及对最坏情况的防御能力。使用时需重点关注索引的正确计算、容器的随机访问特性以及数据是否允许被修改。

手写快速选择？别忘了随机化 pivot 这个关键步骤

若需自行实现快速选择算法，一个至关重要的步骤是随机化选择基准元素。若固定选取首尾元素作为 pivot，当输入数据已排序或接近有序时，算法性能将不可避免地退化为 O(n²)。尽管C++标准库的 std::nth_element 已内置随机化策略，但在手动编码时此点极易被忽略。

一个可靠的建议是：使用 std::random_device 和 std::mt19937 这类现代、高质量的随机数生成器来选取随机索引，并将该位置的元素交换至分区边界。应避免使用传统的 rand() 函数，因其随机性质量不高且不具备线程安全特性。

以下代码片段展示了集成随机化 pivot 选择的快速选择函数核心逻辑：

int quickselect(std::vector& arr, int left, int right, int k) {
    if (left == right) return arr[left];
    std::random_device rd;
    std::mt19937 g(rd());
    std::uniform_int_distribution dist(left, right);
    std::swap(arr[dist(g)], arr[right]); // 随机换 pivot 到末尾
    int pivot_idx = partition(arr, left, right);
    if (k == pivot_idx) return arr[k];
    else if (k < pivot_idx) return quickselect(arr, left, pivot_idx - 1, k);
    else return quickselect(arr, pivot_idx + 1, right, k);
}

立即学习“C++免费学习笔记（深入）”；

理解 std::nth_element 的行为边界与 const 安全性

深入理解 std::nth_element 的行为边界至关重要。该算法仅保证执行后，指定位置（第 k 个）的元素是其最终排序后应处的位置，且其左侧所有元素均不大于它，右侧所有元素均不小于它。但它并不保证前半部分或后半部分内部是有序的。对于单纯获取中位数的目标，这已完全足够，但切勿误用它来获取部分有序的数组。

另一个常被忽视的要点是其对数据的修改性。该算法会原地修改容器内容，因此若传入一个 const std::vector& 类型的引用，将导致编译错误。若原始数据不可更改，务必先创建副本（如 std::vector copy = original;）。忽略此点可能引发运行时崩溃或隐蔽的逻辑缺陷。

• 当参数 k 超出容器有效范围 [0, size) 时，其行为是未定义的，且不会抛出异常。因此，必须检查 k = size/2 的合法性，特别是在容器可能为空（size()==0）的场景下。
• 对于 float、double 或自定义类型，需确保 < 运算符可用且满足严格弱序。通过传入自定义比较器如 std::greater{}，可以方便地查找第 k 大的元素。
• 在性能极度敏感的应用（如高频交易系统）中，应避免反复构造 vector 副本。可考虑复用缓冲区或采用 C++20 的 std::span 来获得一个非拥有的数据视图，以减少拷贝开销。

厘清中位数计算中绕人的索引细节

计算中位数时，最易混淆的环节在于索引的精确换算。关键在于区分“顺序统计量”（第几小）与简单的“数组中间下标”。例如，对于数组 {1,2,3,4}（size=4），数学中位数为 (2+3)/2=2.5，这对应的是第2小（index=1）和第3小（index=2）的元素。而直接使用 size/2 得到的是2（0起始下标），恰好是后者。若错误地在奇数长度情况下使用 (size-1)/2，则会导致结果错位。

一个统一且无需判断奇偶的稳健做法是定义两个位置：k1 = (size-1)/2 和 k2 = size/2（使用整数除法）。当数组长度为奇数时，两者相等；为偶数时，两者相邻。

• 奇数长度：调用 std::nth_element(v.begin(), v.begin() + v.size()/2, v.end())，然后直接访问 v[v.size()/2] 即可获得中位数。
• 偶数长度：必须分别获取 v[(size-1)/2] 和 v[size/2] 的值并计算平均值。注意，不能仅调用一次 nth_element 就试图同时读取这两个相邻位置，因为算法只保证目标位置（k）的元素准确，其相邻元素的相对顺序并未确定。
• 对于超大型数组，使用 std::vector::data() 获取原始指针再结合 std::nth_element，有时可以规避迭代器带来的微小性能开销。

综上所述，在绝大多数实际C++项目中，95%的中位数查找需求，通过结合 std::nth_element 与严谨的索引处理逻辑即可完美解决。自行实现快速选择算法，通常仅在需要精细定制 pivot 选择策略，或处于缺乏标准模板库的嵌入式开发环境时才有必要。真正的挑战往往在于确保索引计算的绝对准确，而非算法本身的复杂性。