快速选择算法（Quickselect） 快速选择算法是一种用于在未排序的列表中找到第k小（或第k大）元素的高效算法。它由托尼·霍尔在1961年提出，是快速排序算法的一个变种。与快速排序平均O(n log n)的时间复杂度不同，快速选择算法在平均情况下具有O(n)的时间复杂度，最坏情况下为O(n²)，但通过优化可以避免最坏情况。 算法核心思想 快速选择基于分治策略，其核心思想是“分区（Partition）”。与快速排序对两个子数组都进行递归不同，快速选择只对包含目标元素的那个子数组进行递归，从而减少了操作次数。 算法步骤详解 选择主元（Pivot Selection） 从当前数组中选择一个元素作为主元。主元的选择会影响算法效率，常见策略包括选择第一个元素、最后一个元素、随机元素或中位数的中位数。 分区操作（Partitioning） 重新排列数组，使得所有小于主元的元素移到其左侧，所有大于主元的元素移到其右侧。此时，主元处于最终排序后的正确位置，其索引记为 pivot_index 。 分区过程通常使用Lomuto分区方案或Hoare分区方案。 判断与递归（Decision & Recursion） 将 pivot_index 与k进行比较： 如果 pivot_index == k-1 （假设k是从1开始计数的第k小），则主元即为所求元素，返回它。 如果 pivot_index > k-1 ，说明第k小的元素位于主元左侧的子数组中，仅对左子数组 arr[left..pivot_index-1] 递归进行快速选择。 如果 pivot_index < k-1 ，说明第k小的元素位于主元右侧的子数组中，仅对右子数组 arr[pivot_index+1..right] 递归进行快速选择。注意，因为左半部分和主元已经贡献了 pivot_index+1 个比目标小的元素，所以在右子数组中寻找的是第 (k - (pivot_index + 1)) 小的元素。 举例说明 假设要在数组 arr = [3, 2, 1, 5, 6, 4] 中找到第2小的元素（k=2）。 初始调用 ： quickselect(arr, 0, 5, 2) 选择主元 ：随机选择主元，假设选到 3 （索引0）。 分区 ：围绕 3 分区，数组变为 [2, 1, 3, 5, 6, 4] 。主元 3 的索引 pivot_index=2 。 判断 ： pivot_index (2) 与 k-1 (1) 比较。因为 2 > 1 ，所以第2小的元素在左子数组 [2, 1] 中。 递归左子数组 ： quickselect(arr, 0, 1, 2) 在子数组 [2, 1] 中选择主元（如选 2 ）。 分区：围绕 2 分区，子数组变为 [1, 2] 。主元 2 的 pivot_index=1 （在全局数组中是索引1，但在当前子数组的局部视角下，其相对索引是1，对应全局索引计算需注意，但判断时用相对索引即可）。这里在子数组 [2, 1] 中，假设我们以第一个元素 2 为主元，分区后为 [1, 2] ，主元 2 位于新索引1（子数组内）。 判断： pivot_index (1) 与 k-1 (1) 比较，相等。因此，主元 2 就是第2小的元素。返回 2 。 时间复杂度分析 最坏情况 ：O(n²)。当每次选择的主元都是当前数组的最小或最大元素，导致每次分区只能减少一个元素。 平均情况 ：O(n)。通过数学期望可以证明，每次分区大约能将问题规模减半，总比较次数约为n + n/2 + n/4 + ... ≈ 2n，因此是线性复杂度。 最佳情况 ：O(n)。每次分区都能将数组均匀划分。 优化策略 为了避免最坏情况O(n²)，通常采用以下优化： 随机化主元 ：随机选择主元，使得算法在期望上达到O(n)。 中位数的中位数 ：使用一个更复杂的策略来选择主元，确保每次分区至少能将数组划分为一定比例（如30%-70%），从而将最坏情况复杂度严格限制在O(n)。这是BFPRT算法的基础。 快速选择算法是解决“Top K”问题（如寻找第k小的元素、前k小的元素）的高效工具，在实际应用中广泛使用。