快速选择算法通过分区思想在o(n)平均时间内找到第k大元素，其核心是将问题转化为查找升序第(n−k)小元素，并递归收缩搜索区间。
一、快速选择算法基本原理
快速选择算法是基于快速排序分区思想的高效查找算法，用于在未完全排序的数组中定位第K大元素的索引位置。其核心在于每次分区后根据基准元素的位置与目标序号的关系，仅递归处理包含目标元素的一侧子区间，从而避免完整排序带来的冗余计算。
二、确定第K大对应的目标索引
给定长度为n的数组，第K大元素等价于升序排列后下标为n−K的元素（0起始索引）。因此需将原始问题转化为在数组中查找升序第(n−K)小元素的位置。
1、计算目标秩r = n - K；
2、确保r在合法范围内：0 ≤ r
3、若K超出[1, n]范围，则返回无效索引-1；
三、分区操作实现
分区过程选取一个主元（pivot），将数组划分为三部分：小于主元的左侧、等于主元的中部、大于主元的右侧。返回左右边界索引，供后续判断目标位置归属。
1、随机选取一个索引i ∈ [left, right]，交换arr[i]与arr[right]；
2、设pivot = arr[right]，初始化lt = left - 1，gt = right + 1，i = left；
3、当i pivot，则交换arr[--gt]与arr[i]；否则i++；
4、最终返回区间[lt + 1, gt - 1]作为主元所在相等段的左右边界；
四、递归收缩搜索区间
根据分区结果与目标秩r的相对关系，决定下一步搜索范围：若r落在相等段内则直接返回任意该段索引；若r小于lt+1则向左子区间递归；若r大于gt−1则向右子区间递归。
1、调用partition(arr, left, right)获取相等段边界[lt+1, gt−1]；
2、若r ∈ [lt + 1, gt - 1]，则返回r作为第K大元素的索引位置；
3、若r ≤ lt，则递归调用quickSelect(arr, left, lt, r)；
4、若r ≥ gt，则递归调用quickSelect(arr, gt, right, r)；
五、平均时间复杂度推导
每次分区以常数概率将数组大致等分为两半，期望递归深度为O(log n)，每层处理总规模为O(n)，故平均时间复杂度为O(n)。最坏情形下每次选到极值作为主元，导致退化为O(n²)，但通过随机化主元选择可有效规避。
1、设T(n)为处理n个元素的期望时间；
2、有T(n) ≤ (1/n) × Σₖ₌₀ⁿ⁻¹ [T(k) + T(n−1−k)] + O(n)；
3、解得T(n) = O(n)，其中O(n)为严格线性平均复杂度；
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
