快速选择算法通过原地分区直接定位第k小元素，避免全排序：奇数长度取arr[n//2]，偶数取arr[n//2-1]与arr[n//2]均值，核心是partition操作确定pivot位置并分治递归。
直接用数组实现快速选择算法找中位数，核心是不排序、只分区、准确定位目标索引。它比先调用 sort() 快得多，尤其在数组大、调用频繁的场景下优势明显。
明确中位数对应的目标位置
对长度为 n 的数组：
- 若 n 为奇数，中位数就是第 (n//2) 小的元素（0-based 索引，即排序后下标为 n//2 的值）；
- 若 n 为偶数，需取第 n//2 - 1 小和第 n//2 小两个元素的平均值。
所以第一步不是算平均，而是能稳定取出第 k 小——这正是快速选择要解决的问题。
数组原地分区：关键操作 partition
用数组实现时，推荐在原数组上做 **in-place 分区**，避免额外空间开销。典型做法：
- 选一个基准（pivot），常用最右/最左/或随机索引；
- 用双指针扫描，把小于 pivot 的元素全挪到左边，大于的挪到右边；
- 最终 pivot 落在某个位置 j，此时它左边有 j - left 个更小元素，意味着它是当前子数组中第 (j - left + 1) 小的数。
- 如果 j == k，直接返回
arr[j]； - 如果 j > k，说明目标在左半段，递归处理
[left, j-1]； - 如果 j ，说明目标在右半段，递归处理
[j+1, right]，注意新 k 是k - j - 1（已排除 j 及左侧元素）。
处理偶数长度的中位数
不能只调一次快速选择就完事。必须分别找出：
- 第 (n//2 - 1) 小的元素（即下标 n//2 - 1）
- 第 (n//2) 小的元素（即下标 n//2）
再求平均。注意：两次调用之间，数组可能被第一次分区打乱，所以要么：
- 对原数组拷贝两份分别处理；
- 或者写成单次调用支持“找两个相邻秩”的优化版本（较复杂，初学建议先复制）。
提升稳定性与效率的小技巧
实际工程中，几个细节影响成败：
- 基准别总选首/尾——容易退化成 O(n²)，改用 随机索引 或 三数取中（取首、中、尾三者中位数）；
- 小数组（如长度
- 使用迭代代替递归，防止栈溢出（尤其数据量达百万级时）；
- C++/Go 等语言注意传参方式：用引用或指针操作原数组，避免无谓拷贝。
