排序算法之：快速选择算法（Quickselect）的进阶应用与中位数的中位数（Median-of-Medians）优化 题目描述 给定一个未排序的整数数组 nums 和一个整数 k （1 ≤ k ≤ nums.length），要求在不完全排序整个数组的情况下，找出数组中第 k 个最小的元素。例如，在数组 [3, 2, 1, 5, 4] 中，第 3 个最小的元素是 3。这个问题是经典的选择问题，可以用快速选择算法解决，但其最坏情况时间复杂度为 O(n²)。本题的进阶部分是：如何优化快速选择算法，使其在最坏情况下也能达到线性时间复杂度 O(n)？这需要用到“中位数的中位数”选择策略。 解题过程循序渐进讲解 第一步：理解快速选择（Quickselect）的基本思想 快速选择是快速排序的变种，核心是“分区”操作。假设我们要找第 k 小的元素（k 从 1 开始计数）： 在数组中随机选择一个元素作为“枢纽元”。 执行分区操作，将数组分成三部分： 小于枢纽元的元素 等于枢纽元的元素 大于枢纽元的元素 分区后，枢纽元的位置就确定了。假设小于枢纽元的元素有 L 个，等于枢纽元的元素有 M 个。 如果 k ≤ L，说明第 k 小的元素在左侧分区，递归在左侧分区中查找第 k 小的元素。 如果 L < k ≤ L + M，说明枢纽元正好是第 k 小的元素，直接返回枢纽元。 如果 k > L + M，说明第 k 小的元素在右侧分区，递归在右侧分区中查找第 k - (L + M) 小的元素。 示例：数组 [3, 6, 2, 1, 5, 4] ，找第 3 小的元素。随机选枢纽元 3，分区后得到 [2, 1] 、 [3] 、 [6, 5, 4] 。此时 L=2，M=1。因为 k=3 满足 L < 3 ≤ L+M（即 2 < 3 ≤ 3），所以枢纽元 3 就是答案。 第二步：分析快速选择的最坏情况与平均复杂度 如果每次选择的枢纽元都是当前分区的最大或最小元素，那么每次只能排除一个元素，递归深度会达到 O(n)，导致总比较次数为 n + (n-1) + ... + 1 = O(n²)，这就是最坏情况。平均情况下，如果枢纽元随机选择，每次能排除大约一半的元素，时间复杂度为 O(n)。但我们需要保证最坏情况也是 O(n)，这就需要优化枢纽元的选择策略。 第三步：引入“中位数的中位数”策略（Median of Medians, BFPRT） 目标：找到一个“足够好”的枢纽元，使得分区后，左右两侧分区的元素数量都至少是原数组大小的一个固定比例（例如至少 3/10）。这样递归深度就能控制在 O(log n)，每次递归处理的数据规模递减，总工作量就是 O(n)。 具体步骤： 将数组分成每组 5 个元素的小组（最后一组可能不足 5 个）。 对每个小组内部进行排序（因为小组大小固定为 5，所以排序时间是常数 O(1) 每组），然后找出每个小组的中位数。 递归调用选择算法，从这些中位数组成的数组中，找出其中位数（即“中位数的中位数”）。这个递归查找的规模是 n/5。 将这个“中位数的中位数”作为枢纽元，进行分区。 为什么这个枢纽元是“足够好”的？ 有一半的小组（即 n/10 个小组）的中位数小于或等于枢纽元。 在每个这样的小组中，至少有 3 个元素（包括中位数本身和比中位数小的两个元素）小于或等于枢纽元。 因此，至少有 3 * (n/10) = 3n/10 个元素小于或等于枢纽元。同理，至少有 3n/10 个元素大于或等于枢纽元。 这意味着分区后，左右两侧分区的大小都至少为 3n/10，最多为 7n/10。递归式：T(n) ≤ T(n/5) + T(7n/10) + O(n)。可以证明 T(n) = O(n)。 第四步：算法实现细节 如果数组大小 n ≤ 5，直接排序并返回第 k 小的元素。 将数组分成大小为 5 的组，对每组排序，取出每组的中位数，组成一个新的数组 medians 。 递归调用快速选择算法，在 medians 中找其中位数 pivot （即第 medians.length/2 小的元素）。 用 pivot 对原数组进行分区，得到左、中、右三个分区。 根据 k 与左、中分区元素数量的关系，决定递归查找的方向。 第五步：复杂度分析 分组和找中位数：O(n) 时间，因为每组排序是常数时间，有 n/5 组。 递归找中位数的中位数：T(n/5)。 分区：O(n)。 递归处理一个最大为 7n/10 的分区：T(7n/10)。 总递归式：T(n) ≤ T(n/5) + T(7n/10) + O(n)。 用代入法可证明 T(n) = O(n)。最坏情况下的线性时间复杂度得以保证。 第六步：举例说明 数组： [12, 3, 5, 7, 4, 19, 26, 30, 1, 6, 2, 8, 14] ，找第 6 小的元素。 分组（5个一组）并找各组中位数： 组1: [ 12,3,5,7,4] → 排序 [ 3,4,5,7,12 ] → 中位数 5 组2: [ 19,26,30,1,6] → 排序 [ 1,6,19,26,30 ] → 中位数 19 组3: [ 2,8,14] → 排序 [ 2,8,14 ] → 中位数 8 中位数数组: [ 5, 19, 8]，找其中位数：排序 [ 5,8,19 ] → 中位数 8。 以 8 为枢纽元分区：小于 8: [ 3,5,4,1,6,2]；等于 8: [ 8]；大于 8: [ 12,7,19,26,30,14 ]。 左分区大小 L=6，M=1。k=6，满足 L < k ≤ L+M（6 < 6 ≤ 7）？不，因为 k=6 正好等于 L=6，所以应在左分区找第 6 小的元素。 在左分区 [ 3,5,4,1,6,2] 中递归查找第 6 小的元素（即整个分区第 6 小）。排序后为 [ 1,2,3,4,5,6 ]，第 6 小是 6，即最终答案。 第七步：总结 通过“中位数的中位数”策略，快速选择算法的最坏情况时间复杂度从 O(n²) 优化为 O(n)。虽然常数因子较大，但保证了线性时间，适用于对最坏情况有严格要求的场景（如实时系统）。这个优化是理论上的经典成果，在实际中，随机化快速选择通常更简单且平均性能很好，但最坏情况无法保证。