Python中的Quickselect算法

在接下来的教程中，我们将学习 Python 中 Quickselect 算法的实现。

但在我们开始之前，让我们先来讨论一下 Quickselect 算法是什么。

什么是 Quickselect 算法？

Quickselect 是一种选择过程，用于识别无序列表中的第 k 个顺序统计量，即最小数据元素。Quickselect 算法利用了与 Quicksort 算法整体相似的方法。

示例

该算法类似于 QuickSort。唯一的区别是，在找到枢轴后，它只在包含第 k 个最小元素的子部分进行递归，而不是在两个部分都进行递归。这个想法很简单：如果分区元素的索引大于 k，我们就对左侧部分进行递归。如果索引等于 k，我们返回，因为我们已经找到了第 k 个最小的元素。如果索引小于 k，则对右侧部分进行递归。预期的复杂度从 O(n log n) 降低到 O(n)，最坏情况下的复杂度为 O(n^2)。

伪代码

Python 中 Quickselect 算法的实现

说明

该算法围绕枢轴元素将数组分区，并通过确定分区索引是否对应于所需的第 k 个位置，使用 Quick Select 技术来查找未排序数组中第 k 个最小的元素。

输出

 
The k-th smallest element is: 6   

重要提示

• 与 quicksort 类似，它在最坏情况下的性能很差，但在实践中速度很快。它用于
• 只有递归代码与 QuickSort 的分区过程不同。
• 在最坏的情况下，有一种算法可以在 O(n) 时间内找到第 k 个最小的元素，尽管 QuickSelect 通常效果更好。