快速选择算法基于分治思想，通过Lomuto或Hoare分区定位第K大元素：每次分区后根据大于/等于基准的元素个数与K的关系，仅递归处理目标子区间，期望时间复杂度O(n)，空间复杂度O(log n)。
一、快速选择算法的基本原理
快速选择算法是基于快速排序分区思想的高效查找算法，用于在未完全排序的数组中定位第K大元素的索引位置。其核心在于每次分区后根据基准元素的位置与目标秩的关系，仅递归处理包含目标元素的一侧子区间，从而避免完整排序带来的冗余计算。
1、将数组划分为三部分：小于基准值的部分、等于基准值的部分、大于基准值的部分。
2、计算大于基准值部分的元素个数，记为greater_count；计算等于基准值部分的元素个数，记为equal_count。
3、若K ≤ greater_count，则第K大元素位于大于基准值的子区间中，递归查找该区间。
立即学习“C++免费学习笔记（深入）”；
4、若K > greater_count + equal_count，则第K大元素位于小于基准值的子区间中，递归查找该区间，并更新K为K − greater_count − equal_count。
5、否则，第K大元素即为基准值本身，返回任意一个等于基准值的索引位置。
二、基于Lomuto分区方案的实现逻辑
该方案采用单指针扫描方式完成分区，代码简洁且易于理解，适用于教学和中小规模数据。分区过程中维护一个指向小于基准值区域右边界的位置变量，遍历时将小于基准的元素逐步交换至左侧。
1、选取最后一个元素作为基准（pivot）。
2、初始化索引i = low，用于标记小于基准值区域的右边界。
3、遍历j从low到high−1，若arr[j] ≥ pivot（注意：为求第K大，使用≥而非≤），则交换arr[i]与arr[j]，并令i++。
4、将基准元素arr[high]与arr[i]交换，此时i为基准在分区后的确切位置。
5、比较i与目标位置target_idx（即降序排列下第K个位置，对应升序索引为n−K），决定递归方向。
三、基于Hoare分区方案的优化实现逻辑
Hoare分区通过双向扫描减少交换次数，在实际运行中通常比Lomuto方案更快。它不保证基准最终落于其排序后位置，但能更紧凑地划分大小区域，适合对性能敏感的场景。
1、选取首元素arr[low]为基准。
2、设置左右指针i = low − 1、j = high + 1。
3、内层循环：从左向右移动i，直到arr[i] ≥ pivot；从右向左移动j，直到arr[j] ≤ pivot。
4、若i ，交换arr[i]与arr[j]；否则终止分区。
5、返回j作为分界点，依据j与target_idx关系决定递归调用范围。
四、随机化基准选择以避免最坏情况
确定性选取首/尾元素作基准可能导致O(n²)时间复杂度（如已排序数组）。引入随机化可在期望意义上消除输入依赖性，使算法在任意输入下保持平均线性性能。
1、在当前子区间[low, high]中生成一个随机整数rand_idx。
2、交换arr[rand_idx]与arr[high]（或arr[low]，视分区方案而定）。
3、后续按原分区逻辑执行，此时基准值服从均匀分布，各次分区大小期望为1:1。
4、重复该过程于每次递归调用前，确保每层递归的基准独立同分布。
五、平均时间复杂度推导逻辑
设T(n)为处理n个元素的期望时间。每次分区后，算法以等概率落在任一位置，但仅递归处理包含第K大元素的子问题。关键观察是：每次成功分区后，剩余处理规模期望不超过3n/4。
1、定义指示变量X_i表示第i轮是否仍需继续递归，X_i = 1当且仅当当前子问题规模 > 3n/4。
2、由几何分布性质，期望递归深度为O(log n)，每层分区耗时O(当前规模)。
3、总期望时间为T(n) = n + T(n/2)的主定理解，或更严格地，T(n) ≤ cn + (1/2)T(n) + (1/2)T(n)，解得T(n) = O(n)。
4、常数因子隐含于分区操作的比较与交换开销中，实际系数约为3~4倍于n。
5、空间复杂度为O(log n)，源于递归栈深度，尾递归优化可降至O(1)。
