数组快速选择找第 K 小值实战教程

想在无序数组中高效找出第K小的元素，却不想耗费O(n log n)时间去完整排序？快速选择算法正是你的最优解——它巧妙改编自快速排序，通过随机化基准选择和三段式分区（小于/等于/大于），平均仅需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：

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：

数组会被原地部分重排，但无需额外空间；若需保持原数组不变，传入副本即可。

以上就是《数组快速选择找第 K 小值实战教程》的详细内容，更多关于的资料请关注golang学习网公众号！