快速选择算法（Quickselect）

题目描述：给定一个未排序的整数数组和一个整数k，设计算法找到数组中第k小的元素。要求平均时间复杂度为O(n)，最坏情况下为O(n²)，空间复杂度为O(1)。

解题过程：

1. 问题分析

   • 这是选择问题的一种，与排序密切相关但不需要完全排序
   • 直接排序后取第k个元素需要O(n log n)时间，但我们希望更高效
   • 快速选择基于快速排序的分区思想，但每次只处理包含目标的那部分

2. 算法核心思想

   • 随机选择一个枢轴元素（pivot）
   • 将数组分为三部分：小于枢轴、等于枢轴、大于枢轴
   • 根据k值所在范围，决定继续处理哪个分区

3. 详细步骤

   • 步骤1：在当前区间[left, right]内随机选择枢轴
   • 步骤2：执行三路分区（荷兰国旗算法）
     • 初始化：i = left, j = left, k = right
     • 遍历：比较元素与枢轴，小的放左边，大的放右边
   • 步骤3：分区后得到三个区间
     • [left, i-1]：小于枢轴的元素
     • [i, j]：等于枢轴的元素
     • [j+1, right]：大于枢轴的元素
   • 步骤4：判断k所在区间
     • 若k ∈ [left, i-1]：在左区间递归查找
     • 若k ∈ [i, j]：枢轴就是第k小元素
     • 若k ∈ [j+1, right]：在右区间递归查找

4. 关键优化点

   • 随机化枢轴选择避免最坏情况
   • 三路分区处理重复元素
   • 每次递归只处理一个分区

5. 复杂度分析

   • 平均情况：每次分区后问题规模减半，T(n) = T(n/2) + O(n) → O(n)
   • 最坏情况：每次选到最值，T(n) = T(n-1) + O(n) → O(n²)
   • 空间：尾递归优化后为O(1)

6. 与快速排序的区别

   • 快速排序需要处理两个分区，而快速选择只处理一个
   • 这正是时间复杂度从O(n log n)降到O(n)的关键