排序算法之：快速选择算法（Quickselect）的进阶应用与中位数的中位数（Median-of-Medians）优化
字数 2553 2025-12-13 03:22:47

排序算法之：快速选择算法（Quickselect）的进阶应用与中位数的中位数（Median-of-Medians）优化

题目描述
快速选择算法（Quickselect）是基于快速排序分治思想的一种选择算法，用于在未排序的数组中找到第k小（或第k大）的元素。与完整排序不同，它平均能在O(n)时间内完成任务。然而，最坏情况下（例如每次选取的主元都是最小或最大元素），其时间复杂度会退化为O(n²)。本题要求你理解快速选择的基本原理，并进一步学习一种保证最坏情况O(n)时间复杂度的方法——中位数的中位数（Median-of-Medians）优化，同时掌握其实现细节和正确性分析。

解题过程循序渐进讲解
我将分步骤讲解快速选择算法及其优化，确保每个细节清晰。

第一步：快速选择的基本思想
快速选择脱胎于快速排序的分区（Partition）过程。快速排序通过选择一个主元（pivot）将数组分为两部分：小于主元的在左，大于等于主元的在右，然后递归排序两边。快速选择则利用这个性质：

  1. 对数组进行一次分区，得到主元的最终位置索引p。
  2. 比较p与目标索引k（寻找第k小的元素，索引通常以0起始，即第0小是最小值）。
    • 如果p == k，则主元恰好是第k小的元素，直接返回。
    • 如果p > k，说明第k小的元素在左半部分，只需递归在左半部分查找。
    • 如果p < k，说明第k小的元素在右半部分，递归在右半部分查找，注意此时目标在右半部分中的新位置是k - (p + 1)。

这样做避免了完全排序，平均时间复杂度为O(n)，因为每次递归处理的规模期望减半：n + n/2 + n/4 + ... ≈ 2n = O(n)。但最坏情况下（例如数组已排序且每次选第一个元素为主元），会退化为O(n²)。

第二步：快速选择的简单实现示例
以找第k小（0 ≤ k < n）为例，使用Lomuto分区（易于理解）。Lomuto分区选择最后一个元素为主元，维护一个指针i，使得区间[0, i]内的元素都小于等于主元。
分区步骤：

  1. 选择最后一个元素作为主元pivot。
  2. 初始化i = low - 1。
  3. 遍历j从low到high-1，如果arr[j] <= pivot，则i++，并交换arr[i]和arr[j]。
  4. 最后交换arr[i+1]和arr[high]，使主元归位，返回主元位置i+1。

快速选择函数quickSelect(arr, low, high, k)：

  • 如果low == high，返回arr[low]。
  • 执行分区得到p = partition(arr, low, high)。
  • 如果p == k，返回arr[p]。
  • 如果p > k，递归调用quickSelect(arr, low, p-1, k)。
  • 否则，递归调用quickSelect(arr, p+1, high, k)。

第三步：最坏情况分析与改进动机
最坏情况发生在每次分区都极度不平衡时，例如数组已排序且每次选最右边元素为主元，每次分区只减少一个元素，导致递归深度为n，比较次数为n + (n-1) + ... + 1 = O(n²)。这在实际应用（如寻找中位数）中不可接受。我们需要一种能保证每次分区相对均衡的主元选择策略。

第四步：中位数的中位数（Median-of-Medians）方法
这是一种确定性选择主元的算法，保证每次分区至少能将数组分为3:7的比例，从而确保最坏情况时间复杂度为O(n)。步骤如下：

  1. 将数组分组：将数组划分为大小为5的小组（最后一组可能少于5个元素）。
  2. 求每组中位数：对每个小组进行插入排序（因为5很小，插入排序简单高效），找出其中位数。
  3. 递归求中位数的中位数：将这些中位数放入一个新数组，递归调用快速选择算法本身，找出这个新数组的中位数（即中位数的中位数，简称MoM）。
  4. 使用MoM作为主元：用这个MoM作为分区的主元。

为什么这样做有效？因为MoM保证了至少有(n/5)/2 ≈ n/10个小组的中位数小于等于它，而每个这样的小组中至少3个元素（包括中位数本身）小于等于该中位数，所以总共至少有3 * (n/10) ≈ 0.3n个元素小于等于MoM。同理，至少有0.3n个元素大于等于MoM。因此，分区后左右两部分的大小都不会超过0.7n。这就保证了递归规模每次至少减少30%。

第五步：时间复杂度证明
设T(n)为算法在最坏情况下的时间复杂度。

  • 分组和找小组中位数：每组5个，插入排序O(1)，有⌈n/5⌉组，总时间O(n)。
  • 递归求MoM：新数组大小为⌈n/5⌉，时间T(n/5)。
  • 分区：用MoM分区，时间O(n)。
  • 递归调用：分区后，子问题规模最大为0.7n，时间最多T(0.7n)。
    因此递归式：T(n) ≤ T(n/5) + T(0.7n) + O(n)。
    可以证明（用代入法或主定理扩展形式）T(n) = O(n)。具体证明：假设T(n) ≤ cn，代入得cn/5 + 0.7cn + an ≤ cn，解得c ≥ 10a，成立。所以最坏情况O(n)。

第六步：实现细节与注意事项
实现时需要小心：

  • 当数组规模很小时（如n ≤ 5），直接排序并返回第k个元素。
  • 分区时，先找到MoM的值，然后在数组中找到它的位置（或使用三数取中法调整），然后交换到末尾作为主元进行标准分区。
  • 由于常数因子较大，MoM方法在实际中通常比随机化快速选择慢，因此常用于对最坏时间有严格要求的场景。

第八步：应用与扩展
快速选择不仅用于找第k小，还可用于：

  • 找中位数（k = n/2）。
  • 找百分位数。
  • 快速找出前k个最小（或最大）元素（不完全排序，用快速选择分区后，前k个就在左侧，然后可单独排序左侧，总时间O(n + k log k)）。

总结
快速选择算法通过分治策略高效选择第k小元素，平均O(n)但最坏O(n²)。中位数的中位数优化通过精心选择主元，保证了最坏情况O(n)的时间复杂度，虽然常数较大但理论意义重要。理解这个优化有助于深入掌握分治算法的设计技巧和复杂度分析方法。

排序算法之：快速选择算法（Quickselect）的进阶应用与中位数的中位数（Median-of-Medians）优化 题目描述 快速选择算法（Quickselect）是基于快速排序分治思想的一种选择算法，用于在未排序的数组中找到第k小（或第k大）的元素。与完整排序不同，它平均能在O(n)时间内完成任务。然而，最坏情况下（例如每次选取的主元都是最小或最大元素），其时间复杂度会退化为O(n²)。本题要求你理解快速选择的基本原理，并进一步学习一种保证最坏情况O(n)时间复杂度的方法——中位数的中位数（Median-of-Medians）优化，同时掌握其实现细节和正确性分析。 解题过程循序渐进讲解 我将分步骤讲解快速选择算法及其优化，确保每个细节清晰。 第一步：快速选择的基本思想 快速选择脱胎于快速排序的分区（Partition）过程。快速排序通过选择一个主元（pivot）将数组分为两部分：小于主元的在左，大于等于主元的在右，然后递归排序两边。快速选择则利用这个性质： 对数组进行一次分区，得到主元的最终位置索引 p 。 比较 p 与目标索引 k （寻找第k小的元素，索引通常以0起始，即第0小是最小值）。 如果 p == k ，则主元恰好是第k小的元素，直接返回。 如果 p > k ，说明第k小的元素在左半部分，只需递归在左半部分查找。 如果 p < k ，说明第k小的元素在右半部分，递归在右半部分查找，注意此时目标在右半部分中的新位置是 k - (p + 1) 。 这样做避免了完全排序，平均时间复杂度为O(n)，因为每次递归处理的规模期望减半：n + n/2 + n/4 + ... ≈ 2n = O(n)。但最坏情况下（例如数组已排序且每次选第一个元素为主元），会退化为O(n²)。 第二步：快速选择的简单实现示例 以找第k小（0 ≤ k < n）为例，使用Lomuto分区（易于理解）。Lomuto分区选择最后一个元素为主元，维护一个指针 i ，使得区间 [0, i] 内的元素都小于等于主元。 分区步骤： 选择最后一个元素作为主元 pivot 。 初始化 i = low - 1 。 遍历 j 从 low 到 high-1 ，如果 arr[j] <= pivot ，则 i++ ，并交换 arr[i] 和 arr[j] 。 最后交换 arr[i+1] 和 arr[high] ，使主元归位，返回主元位置 i+1 。 快速选择函数 quickSelect(arr, low, high, k) ： 如果 low == high ，返回 arr[low] 。 执行分区得到 p = partition(arr, low, high) 。 如果 p == k ，返回 arr[p] 。 如果 p > k ，递归调用 quickSelect(arr, low, p-1, k) 。 否则，递归调用 quickSelect(arr, p+1, high, k) 。 第三步：最坏情况分析与改进动机 最坏情况发生在每次分区都极度不平衡时，例如数组已排序且每次选最右边元素为主元，每次分区只减少一个元素，导致递归深度为n，比较次数为n + (n-1) + ... + 1 = O(n²)。这在实际应用（如寻找中位数）中不可接受。我们需要一种能保证每次分区相对均衡的主元选择策略。 第四步：中位数的中位数（Median-of-Medians）方法 这是一种确定性选择主元的算法，保证每次分区至少能将数组分为3:7的比例，从而确保最坏情况时间复杂度为O(n)。步骤如下： 将数组分组 ：将数组划分为大小为5的小组（最后一组可能少于5个元素）。 求每组中位数 ：对每个小组进行插入排序（因为5很小，插入排序简单高效），找出其中位数。 递归求中位数的中位数 ：将这些中位数放入一个新数组，递归调用快速选择算法本身，找出这个新数组的中位数（即中位数的中位数，简称MoM）。 使用MoM作为主元 ：用这个MoM作为分区的主元。 为什么这样做有效？因为MoM保证了至少有 (n/5)/2 ≈ n/10 个小组的中位数小于等于它，而每个这样的小组中至少3个元素（包括中位数本身）小于等于该中位数，所以总共至少有 3 * (n/10) ≈ 0.3n 个元素小于等于MoM。同理，至少有0.3n个元素大于等于MoM。因此，分区后左右两部分的大小都不会超过0.7n。这就保证了递归规模每次至少减少30%。 第五步：时间复杂度证明 设T(n)为算法在最坏情况下的时间复杂度。 分组和找小组中位数：每组5个，插入排序O(1)，有⌈n/5⌉组，总时间O(n)。 递归求MoM：新数组大小为⌈n/5⌉，时间T(n/5)。 分区：用MoM分区，时间O(n)。 递归调用：分区后，子问题规模最大为0.7n，时间最多T(0.7n)。 因此递归式：T(n) ≤ T(n/5) + T(0.7n) + O(n)。 可以证明（用代入法或主定理扩展形式）T(n) = O(n)。具体证明：假设T(n) ≤ cn，代入得cn/5 + 0.7cn + an ≤ cn，解得c ≥ 10a，成立。所以最坏情况O(n)。 第六步：实现细节与注意事项 实现时需要小心： 当数组规模很小时（如n ≤ 5），直接排序并返回第k个元素。 分区时，先找到MoM的值，然后在数组中找到它的位置（或使用三数取中法调整），然后交换到末尾作为主元进行标准分区。 由于常数因子较大，MoM方法在实际中通常比随机化快速选择慢，因此常用于对最坏时间有严格要求的场景。 第八步：应用与扩展 快速选择不仅用于找第k小，还可用于： 找中位数（k = n/2）。 找百分位数。 快速找出前k个最小（或最大）元素（不完全排序，用快速选择分区后，前k个就在左侧，然后可单独排序左侧，总时间O(n + k log k)）。 总结 快速选择算法通过分治策略高效选择第k小元素，平均O(n)但最坏O(n²)。中位数的中位数优化通过精心选择主元，保证了最坏情况O(n)的时间复杂度，虽然常数较大但理论意义重要。理解这个优化有助于深入掌握分治算法的设计技巧和复杂度分析方法。