教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载导读QuickSelect快速选择是一种用于在无序列表中查找第 k 小元素的选择算法它与快速排序算法同源可以看作只递归一半的快速排序。本文以 selection_algorithms 目录 的官方说明为骨架结合 Cosmos 仓库中 C、Python、Java、Go、Kotlin、Swift、C、Haskell 等多语言实现系统讲解 QuickSelect 的算法原理、分区过程、复杂度分析、典型应用场景以及如何用中位数中位数Median of Medians把最坏时间复杂度从 O(n²) 稳定到 O(n)。读完本文你将掌握在任意语言中实现并正确使用选择算法的完整能力。1. 什么是 QuickSelect与快速排序的关系QuickSelect 是一种选择算法用于在无序列表中查找第 k 小的元素。它与快速排序算法密切相关。 —— code/selection_algorithms/src/README.md这两者的核心区别体现在递归策略上快速排序选定 pivot 后对左右两侧都进行递归最终使整个数组有序QuickSelect选定 pivot 并完成分区后只递归包含目标元素的那一侧另一侧直接丢弃。仓库中的 C 实现 在注释中明确写出了这一设计要点This algorithm is similar to quicksort because it chooses an element as a pivot and partitions the data into two based on the pivot. However, unlike quicksort, quickselect only recurses into one side - the side with the element it is searching for.正是因为每轮只处理一侧QuickSelect 的平均代价才能从快速排序的 O(n log n) 降到 O(n)。1.1 第 k 小与第 k 大的一体两面quick_select.java 的开头注释给出了一个实用的等价关系Find kth largest element is equivalent to find (n - k)th smallest element in array. It is worth mentioning that (n - k) is the real index (start from 0) of an element.也就是说在长度为 n 的数组中求第 k 大元素等价于求第 n - k 小下标从 0 计数的元素。Java 实现正是利用这一点把findKthLargest(nums, k)转换为寻找下标为nums.length - k的第 k 小元素。这一个等价变换让 QuickSelect 可以统一解决第 k 小和第 k 大两类问题。2. 算法核心随机化分区PartitionQuickSelect 的核心步骤与快速排序的 Lomuto 分区一致仓库中 C 版本 的实现如下int partition(vectorint v, int left, int right, int pivotIndex) { int pivotValue v[pivotIndex]; vSwap(v, pivotIndex, right); // 1. 把 pivot 移到末尾 int storeIndex left; for (int i left; i right; i) // 2. 小于 pivot 的元素依次前移 if (v[i] pivotValue) { vSwap(v, storeIndex, i); storeIndex; } vSwap(v, right, storeIndex); // 3. 把 pivot 放回最终位置 return storeIndex; // 返回 pivot 的最终下标 }整个分区过程分为三步暂存 pivot 值并将其与区间右端元素交换避免在遍历中干扰比较一趟扫描维护storeIndex指针把所有小于 pivot 的元素交换到区间左端扫描完成后storeIndex之前的元素全部 pivot把 pivot 放回storeIndex位置此时 pivot 已处于它在有序数组中的最终位置左边全小、右边全大并返回该位置。在 Python 版本 中随机选择的 pivot 被首先交换到列表开头然后扫描剩余元素完成同样的就地分区Go 版本 则与 C 一致采用pivot 移末尾策略。三种写法本质等价都是 O(right - left) 时间、O(1) 额外空间的就地分区。2.1 随机化 pivot 的选择为了让平均复杂度稳定在 O(n)各实现都使用随机 pivotCint pivotIndex left floor(rand() % (right - left 1));quickselect.cppPythonpivot_index random.randint(l, r)quickselect.pyGopivotIndex : rand.Intn(right)quickselect.goKotlinleft Math.floor((rand.nextInt(MAX) % (right - left 1)).toDouble()).toInt()quick_select.ktSwiftrandom(min: low, max: high)基于arc4random_uniformquick_select.swift随机化 pivot 的意义在于它使算法对几乎有序、几乎逆序等退化输入不再敏感——即使每次分区都极不平衡这种事件发生的概率也随规模指数级降低从而在概率意义上保证了 O(n) 的平均行为。3. 递归选择过程只进入一侧完成分区拿到 pivot 下标后QuickSelect 只需三路判断即可定位答案。以 C 实现 为例int select(vectorint v, int left, int right, int k) { if (left right) return v[k]; // Select a random pivot within left and right int pivotIndex left floor(rand() % (right - left 1)); pivotIndex partition(v, left, right, pivotIndex); if (k pivotIndex) return v[k]; // 1. 命中pivot 就是第 k 小元素 else if (k pivotIndex) return select(v, left, pivotIndex - 1, k); // 2. 目标在左半区 else return select(v, pivotIndex 1, right, k); // 3. 目标在右半区 }递归的终止条件与分支逻辑为终止当区间收缩到left right只剩一个候选元素时该元素必为答案命中若k pivotIndex说明 pivot 恰好落在目标位置直接返回左递归若k pivotIndex目标在左半区[left, pivotIndex - 1]右半区整体丢弃右递归若k pivotIndex目标在右半区[pivotIndex 1, right]左半区整体丢弃。Python 实现 在进入递归前还做了两项输入校验空列表返回None、item_index越界抛出IndexErrorquickselect.py这是工程化实现中值得借鉴的健壮性细节。另外 Go 版本 与 Kotlin 版本 的递归逻辑与 C 完全同构其中 Kotlin 使用了tailrec尾递归优化避免深度递归时的栈开销。4. 复杂度分析平均 O(n)最坏 O(n²)原文档给出的复杂度结论是O(n)最坏情况 O(n²)—— code/selection_algorithms/src/README.md这一结论的推导过程如下4.1 平均情况 O(n)假设每次分区大致平衡即 pivot 位于区间中位附近。规模为 n 时第一轮分区开销为 cn之后只对约 n/2 的一侧递归于是有递推式T(n) T(n/2) cn由主定理或等比数列求和可知 T(n) O(n)。直观理解n n/2 n/4 ... 2n所以总工作量是输入规模的常数倍。随机化 pivot 保证了大致平衡以高概率成立这正是各语言实现都采用随机化的原因。4.2 最坏情况 O(n²)如果 pivot 每次都选到当前区间的最小值或最大值则每轮只排除一个元素递推式退化为T(n) T(n-1) cn累加得 T(n) O(n²)这与快速排序最坏情形同源。需要强调的是选择固定 pivot如始终取第一个元素时对已有序输入必然触发最坏情况而随机 pivot 只是让这种情况的概率极低并不能从理论上消除。若需要严格保证最坏情况 O(n)需采用下一节的中位数中位数算法。4.3 空间复杂度QuickSelect 是就地算法分区只使用常数个临时变量递归深度平均为 O(log n)最坏为 O(n)。Kotlin 版使用tailrec优化后理论上可将递归开销摊薄到常数级quick_select.kt。5. 确定性改进Median of Medians中位数中位数针对随机化无法消除最坏情况的缺陷仓库在 median_of_medians 子目录 提供了确定性选择算法其 C 实现注释开宗明义The median of medians algorithm. Deterministic select algorithm that executes in O(n) in the worst case. —— median_of_medians.c5.1 算法步骤以 Python 实现 为参照核心流程为分组把数组按每 5 个一组切分chunks [A[i : i 5] for i in range(0, len(A), 5)]求各组中位数对每个小组递归调用select(chunk, len(chunk) // 2)取中位数递归求中位数的中位数把上一步得到的 medians 列表再次求中位数得到 pivot 候选medianOfMedians按 pivot 分区将数组分成lowerPartition pivot与upperPartition pivot两部分三路判断若i len(lowerPartition)则 pivot 即答案若i更大则递归右半区并把索引减去左侧长度和 pivot 本身否则递归左半区。C 实现 getMedianOfMedians 用一个循环完成分组 组内插入排序insertionSortmedian_of_medians.c 中位数前置随后递归计算中位数的中位数Haskell 版本则借助chunksOf 5与map median以纯函数风格表达同一流程median_of_medians.hs。5.2 为什么组大小取 5分组大小取 5 是数学推导的结果每组 5 个元素、组数为 n/5中位数的中位数能保证至少有约 3n/10 个元素小于 pivot、约 3n/10 个元素大于 pivot从而每次分区后问题规模最多收缩到约 7n/10。由此得到递推式T(n) T(n/5) T(7n/10) O(n)解得 T(n) O(n)即最坏情况线性时间。若组大小取 3 则无法保证线性界这正是实现中把分组大小硬编码为 5 的原因C 版定义为#define MEDIAN_GROUPS_SIZE 5见 median_of_medians.c。5.3 权衡优点最坏情况复杂度严格为 O(n)无随机性适合对最坏延迟敏感的场景缺点常数因子较大每轮需要求中位数的中位数、多次递归实际运行通常慢于随机化 QuickSelect。因此实践中默认选择仍是随机化 QuickSelect中位数中位数更多作为理论上的确定性上界手段。6. 快速排序还是 QuickSelect排序后取下标的选择仓库中的 Swift 实现 给出了一个最朴素但正确的对照方案public func kthLargest(_ a: [Int], _ k: Int) - Int? { let len a.count if k 0 k len { let sorted a.sorted() return sorted[len - k] } else { return nil } }当数据量很小时直接全量排序再按下标取值O(n log n)实现最简单、不易出错而当 n 较大、或需要频繁求第 k 小元素时QuickSelect 的 O(n) 平均复杂度优势显著。仓库同时提供了第三条路径quickselect_stl.cpp 借助 C 标准库std::nth_element一行完成同样的选择nth_element(v.begin(), v.begin() k, v.end()); cout v[k] endl;std::nth_element保证第 k 个位置上的元素就是排序后应处的元素左侧全 ≤、右侧全 ≥其平均复杂度为线性内部正是 QuickSelect 类算法的工业级实现。三种方案朴素排序、手写 QuickSelect、标准库 nth_element可在不同场景下互相印证。7. 边界条件与正确性要点综合仓库各语言实现使用 QuickSelect 时有以下边界条件需要特别注意要点说明仓库依据空输入Python 实现对空列表返回Nonequickselect.py索引越界k 不在[0, n-1]时抛出异常/返回 nilquickselect.py、quick_select.swift单元素区间left right时直接返回无需再分区quickselect.cpp递归出口当k pivotIndex时立即返回避免无限递归quickselect.cpp第 k 大 ↔ 第 k 小用n - k下标互换quick_select.java就地分区全程在原数组上交换不申请额外数组各语言partition实现C 主函数示例 用一个 20 个元素的随机序列验证select(v, 0, v.size() - 1, 0)能正确返回最小值即第 0 小元素Kotlin 主函数 则对k 0..9依次调用并打印结果可直接观察算法对每个 k 的输出与排序结果的一致性。8. 典型应用场景在实际工程与算法竞赛中QuickSelect 通常用于以下场景求中位数取k n / 2即可在线性时间内得到中位数这也是 Median of Medians 版实现中median函数的用法median_of_medians.hsTop-K 问题求第 k 大元素后其右侧或左侧元素天然构成 Top-K 集合无需完整排序分位数与统计求 p 分位数、数组的众数候选、成绩排名等异常值检测与过滤先定位中位数或特定分位点再以 O(n) 代价划分数据集数据流/批处理预处理在大规模数据排序前先求出阈值元素做分桶。在这些场景中QuickSelect 相比先排序再取下标能省去大量与目标无关的排序工作这正是选择算法存在的意义。9. 总结维度结论算法本质快速排序的半递归变体只处理包含目标元素的一侧平均复杂度O(n)随机化 pivot 保证最坏复杂度O(n²)固定 pivot 退化输入时触发确定性改进Median of Medians分组大小为 5最坏 O(n)空间复杂度就地分区 O(1) 辅助空间递归栈 O(log n) 平均多语言覆盖C、Python、Java、Go、Kotlin、Swift、C、Haskell 八种实现仓库路径选择算法目录Cosmos 仓库在 selection_algorithms 下完整收录了 QuickSelect 的随机化实现与 Median of Medians 确定性实现并配套 测试目录 与 C 标准库封装。若需进一步探索可对照阅读快速排序的完整实现见 divide_conquer 下的 quick_sort理解两者全递归与半递归的差异即可彻底掌握这一 O(n) 选择利器。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐TheAlgorithms/C快速选择算法高效查找无序数组第K小元素的终极指南TheAlgorithms/C快速选择算法高效查找无序数组第K小元素的终极指南 快速选择算法是一种高效的查找无序数组中第K小元素的算法由计算机科学家Tony示例工程Hello 算法Top-k 问题深度剖析——如何用最小堆从无序数组中高效找出最大的 k 个元素Hello 算法Top k 问题深度剖析——如何用最小堆从无序数组中高效找出最大的 k 个元素 Top k 问题Top k Problem是堆heap教程文档示例工程教育LeetCode 230 题解在 BST 中查找第 K 小元素Kth Smallest Integer in a BSTLeetCode 230 题解在 BST 中查找第 K 小元素Kth Smallest Integer in a BST 导读 本题要求在一棵二叉搜索树示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考