快速选择法： 由电脑随机生成 7 个数字。

快速选择法是一种算法，用于从无序列表中快速选择第 k 个最小元素。该算法由 Tony Hoare 于 1961 年发明。

算法步骤

1. 从列表中随机选择一个枢轴元素。
2. 将列表划分为两个子列表：一个包含小于枢轴元素的元素，另一个包含大于或等于枢轴元素的元素。
3. 如果第 k 个最小元素位于较小的子列表中，则递归地将快速选择法应用于较小的子列表。
4. 如果第 k 个最小元素位于较大的子列表中，则递归地将快速选择法应用于较大的子列表。
5. 重复步骤 2-4，直到找到第 k 个最小元素。

例子

考虑以下无序列表：

10, 20, 5, 15, 12, 7, 3

假设我们要找到第 3 个最小元素。

1. 我们随机选择枢轴元素 12。
2. 将列表划分为两个子列表：
   • 较小的子列表：5, 7, 3
   • 较大的子列表：10, 20, 15
3. 第 3 个最小元素位于较大子列表中，因此我们将快速选择法应用于较大子列表。
4. 我们再次随机选择枢轴元素 15。
5. 将较大子列表划分为两个子列表：
   • 较小的子列表：10
   • 较大的子列表：20, 15
6. 第 3 个最小元素位于较小的子列表中，因此我们递归地将快速选择法应用于较小的子列表。
7. 较小的子列表仅包含一个元素 10，因此 10 是第 3 个最小元素。

复杂度分析

• 平均时间复杂度：O(n)
• 最坏时间复杂度：O(n ² )
• 空间复杂度：O(log n)

应用

快速选择法广泛用于各种应用中，包括：

• 查找中位数
• 查找第 k 个最大元素
• 计算分位数
• 快速排序

优点

• 平均时间复杂度为 O(n)
• 易于实现
• 广泛应用于各种问题中

缺点

• 最坏时间复杂度为 O(n ² )
• 需要额外的空间，用于递归调用

总结

快速选择法是一种高效的算法，用于从无序列表中快速选择第 k 个最小元素。该算法具有平均时间复杂度 O(n)，但最坏时间复杂度为 O(n ² )。快速选择法易于实现，广泛应用于各种问题中，包括查找中位数、查找第 k 个最大元素和计算分位数。