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

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

在C++中寻找序列的中位数，std::nth_element 往往是那个被低估的“瑞士军刀”。它能在均摊 O(n) 的复杂度内完成任务，其内部实现正是经过深度优化的快速选择（Quickselect）算法，集成了三数取中、小数组优化和尾递归消除等技巧，有效规避了最坏情况 O(n²) 的性能陷阱。相比之下，直接调用 std::sort 的 O(n log n) 显得大材小用，而 std::partial_sort 在仅需单个中位数时也会进行不必要的额外排序。

具体使用时，有几个关键细节需要把握：

• 对于偶数长度的数组，通常将中位数定义为第 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 是寻找中位数的首选，因为它兼具均摊O(n)的高效性、内置的工业级优化，并能有效规避最坏情况。使用时需留意索引计算、容器的可修改性以及随机访问要求。

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

如果需要自己实现快速选择算法，有一个步骤绝对不能省略：随机化选择基准（pivot）。如果固定选择首尾元素作为 pivot，那么在遇到已排序或逆序数组时，算法性能必然会退化为 O(n²)。虽然C++标准库的实现默认包含了随机化，但自己动手时很容易忽略这一点。

一个实用的建议是：使用 std::random_device 和 std::mt19937 这类高质量的随机数生成器来选取随机索引，并将该位置的元素交换到末尾再进行分区操作。应避免使用传统的 rand() 函数，它不仅随机性质量较低，而且不具备线程安全性。

下面的代码片段展示了一个加入了随机化的快速选择函数核心逻辑：

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) 时，其行为是未定义的（UB），不会抛出异常。因此，务必检查 k = size/2 的合法性，特别是在容器可能为空（size()==0）的情况下。
• 对于 float 类型或自定义类型，需要确保 < 运算符可用且满足严格弱序。通过传入 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，有时可以避免一些迭代器带来的微小开销。

说到底，在实际项目中，95%的中位数查找需求，用 std::nth_element 加上几行严谨的索引处理逻辑就足以完美解决。自己动手实现快速选择算法，通常只在需要精细控制 pivot 选择策略，或者身处没有标准模板库的嵌入式环境时才有必要。真正的挑战往往在于把索引计算准确，而非算法本身有多复杂。