快速选择算法可在o(n)平均时间复杂度内找到无序数组中第k小元素；其通过分区操作将数组分为小于、等于、大于基准的三部分，并根据k与各区长度关系递归收缩查找范围，配合随机化基准选择避免最坏o(n²)性能。
快速选择（QuickSelect）是快速排序的变种，用于在 O(n) 平均时间复杂度内找到无序数组中第 K 小的元素（K 从 1 开始计数）。它不完全排序，只聚焦目标位置，因此比先排序再取索引更高效。
核心思路：分区 + 递归收缩范围
基于快速排序的 partition 操作：选定一个基准（pivot），将数组划分为三部分 —— 小于 pivot 的左区、等于 pivot 的中区、大于 pivot 的右区。通过比较 K 与左区/中区长度，决定下一步在哪个子区间继续查找：
- 若 K ≤ 左区长度 → 第 K 小在左区，递归处理左半段
- 若 K ≤ 左区长度 + 中区长度 → 第 K 小就是 pivot，直接返回
- 否则 → 第 K 小在右区，递归处理右半段，新 K = K − (左区长度 + 中区长度)
避免最坏性能：随机化基准选择
固定选首/尾元素作 pivot 在已排序或近似有序数组上会退化为 O(n²)。实战中应在每次 partition 前，随机交换一个元素到末尾作为 pivot：
// 示例（Python 风格伪代码）import random
def quickselect(nums, left, right, k):
if left == right: return nums[left]
# 随机选 pivot 并换到 right 位置
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
# 执行 partition，返回 pivot 最终下标
pivot_final = partition(nums, left, right)
if k == pivot_final:
return nums[k]
elif k return quickselect(nums, left, pivot_final - 1, k)
else:
return quickselect(nums, pivot_final + 1, right, k)
partition 实现细节（Lomuto 方案）
这是最易理解的分区方式，以末尾元素为 pivot，用单指针维护「小于 pivot 的区域边界」：
- 初始化 i = left，遍历 j 从 left 到 right−1
- 若 nums[j]
- 最后交换 nums[i] 和 nums[right]，返回 i
- 注意：该方案天然将等于 pivot 的元素分散在左右两侧；如需三路分区（提升重复元素性能），可改用荷兰国旗法
实战调用与边界处理
调用时注意 K 是「第 K 小」，对应数组中索引为 k−1（0-based）。例如找最小值即 K=1 → target index = 0；找中位数（奇数长数组）即 K = (n+1)//2：
# 示例：在 [3,2,1,5,6,4] 中找第 2 小值nums = [3,2,1,5,6,4]
k = 2
result = quickselect(nums, 0, len(nums)-1, k-1) # 传入索引 1
print(result) # 输出 2
数组会被原地部分重排，但无需额外空间；若需保持原数组不变，传入副本即可。
