快速选择算法

字数 1172 2025-11-02 19:16:42

快速选择算法

题目描述
快速选择算法（Quickselect）是一种在未排序的数组中找到第k小（或第k大）元素的高效算法，平均时间复杂度为O(n)，最坏情况下为O(n²)。它基于快速排序的分区思想，但只递归处理目标元素所在的那部分数组，从而减少计算量。

解题过程

核心思想：
- 选择一个基准值（pivot），将数组分为三部分：小于基准、等于基准、大于基准。
- 根据第k小的位置与基准的相对位置，决定递归处理左半部分、右半部分，或直接返回基准值。
详细步骤：
步骤1：选择基准值（Pivot）
- 常用方法：随机选择元素、中位数法，或直接取第一个元素（简单但可能效率低）。
- 优化：使用“三数取中法”（取首、中、尾元素的中位数）减少最坏情况概率。
步骤2：分区（Partition）
- 将数组重新排列，使得所有小于基准的元素移到左侧，等于基准的居中，大于基准的移到右侧。
- 分区后，基准值的最终位置即为其排序后的正确位置。
- 示例：
```
数组: [3, 2, 1, 5, 4], pivot=3  
分区后: [1, 2, 3, 5, 4]  
          ^ 基准索引=2  
```
步骤3：判断递归方向
- 设分区后基准的索引为pivot_index，左半部分元素个数为left_count = pivot_index。
- 比较k与left_count：
  - 若k <= left_count：第k小元素在左半部分，递归处理左子数组（< pivot的部分）。
  - 若k > left_count + 等于基准的元素个数：第k小元素在右半部分，递归处理右子数组（> pivot的部分），同时更新k = k - (left_count + 等于基准的元素个数)。
  - 否则，第k小元素就是基准值，直接返回。
举例说明
数组: [3, 2, 1, 5, 4]，找第3小的元素（k=3）。
- 选基准pivot=3，分区后：[1, 2, 3, 5, 4]，pivot_index=2。
- left_count=2（元素1和2），等于基准的元素个数=1（元素3）。
- 判断：k=3 ≤ left_count+1=3？是，但k=3 > left_count=2，说明目标在等于基准的部分，直接返回3。
时间复杂度分析
- 平均情况：每次分区后递归处理一半数组，T(n) = T(n/2) + O(n) → O(n)。
- 最坏情况：每次分区极不平衡（如数组已排序且选到最值作为基准），T(n) = T(n-1) + O(n) → O(n²)。
- 优化：随机化基准选择可避免最坏情况，期望复杂度为O(n)。
与堆排序对比
- 堆排序找第k小需O(n log k)（维护大小为k的堆），快速选择更节省内存（原地操作）。

关键点总结

快速选择是快速排序的变种，通过“分区+定向递归”避免完全排序。
注意处理重复元素：分区时应将等于基准的元素集中放置。
工程中常结合插入排序（小数组直接排序）进一步提升效率。

快速选择算法题目描述快速选择算法（Quickselect）是一种在未排序的数组中找到第k小（或第k大）元素的高效算法，平均时间复杂度为O(n)，最坏情况下为O(n²)。它基于快速排序的分区思想，但只递归处理目标元素所在的那部分数组，从而减少计算量。解题过程核心思想：选择一个基准值（pivot），将数组分为三部分：小于基准、等于基准、大于基准。根据第k小的位置与基准的相对位置，决定递归处理左半部分、右半部分，或直接返回基准值。详细步骤：步骤1：选择基准值（Pivot）常用方法：随机选择元素、中位数法，或直接取第一个元素（简单但可能效率低）。优化：使用“三数取中法”（取首、中、尾元素的中位数）减少最坏情况概率。步骤2：分区（Partition）将数组重新排列，使得所有小于基准的元素移到左侧，等于基准的居中，大于基准的移到右侧。分区后，基准值的最终位置即为其排序后的正确位置。示例：步骤3：判断递归方向设分区后基准的索引为 pivot_index ，左半部分元素个数为 left_count = pivot_index 。比较 k 与 left_count ：若 k <= left_count ：第k小元素在左半部分，递归处理左子数组（ < pivot 的部分）。若 k > left_count + 等于基准的元素个数：第k小元素在右半部分，递归处理右子数组（ > pivot 的部分），同时更新 k = k - (left_count + 等于基准的元素个数) 。否则，第k小元素就是基准值，直接返回。举例说明数组: [3, 2, 1, 5, 4] ，找第3小的元素（k=3）。选基准pivot=3，分区后： [1, 2, 3, 5, 4] ，pivot_ index=2。 left_ count=2（元素1和2），等于基准的元素个数=1（元素3）。判断：k=3 ≤ left_ count+1=3？是，但k=3 > left_ count=2，说明目标在等于基准的部分，直接返回3。时间复杂度分析平均情况：每次分区后递归处理一半数组，T(n) = T(n/2) + O(n) → O(n)。最坏情况：每次分区极不平衡（如数组已排序且选到最值作为基准），T(n) = T(n-1) + O(n) → O(n²)。优化：随机化基准选择可避免最坏情况，期望复杂度为O(n)。与堆排序对比堆排序找第k小需O(n log k)（维护大小为k的堆），快速选择更节省内存（原地操作）。关键点总结快速选择是快速排序的变种，通过“分区+定向递归”避免完全排序。注意处理重复元素：分区时应将等于基准的元素集中放置。工程中常结合插入排序（小数组直接排序）进一步提升效率。