请求协助理解确定性选择算法的实现与时间复杂度分析

我来把这个经典的线性时间确定性选择算法的步骤拆解清楚，它核心是靠「中位数的中位数」来保证划分的平衡性，从而规避快速选择最坏情况的$O(n²)$复杂度：

• 分组阶段：
  把输入的n个元素按每组5个进行划分（这里的5只是常用选择，换成7、9这类奇数都可以，只会影响时间复杂度的常数项，不改变线性性质），每个分组记为$S[i]$，i的取值范围是1到$\lfloor n/5 \rfloor$（如果n不是5的整数倍，最后一组元素数量会少于5）。
  对每个分组$S[i]$，找出它的中位数并记为$x[i]$。每个组找中位数最多需要6次比较，所有组加起来总计$6n/5$次比较——这一步是线性时间的，因为只是对极小的子集做中位数查找。

• 递归找中位数的中位数：
  调用本算法递归处理所有分组中位数组成的集合${x[i]}$，这一步的时间复杂度是$T(n/5)$（这里$T(n)$代表处理n个元素的算法时间复杂度）。
  把这次递归得到的结果记为M，也就是我们说的「中位数的中位数」。

• 划分与递归求解：
  用M作为基准元素，对原始输入的所有元素进行划分，这一步的逻辑和快速选择算法的划分完全一致。划分完成后：

  • 如果我们要找的第k小元素正好对应M的位置，直接返回M；
  • 如果k小于M在划分后的位置，递归调用本算法处理左分区；
  • 如果k大于M的位置，递归调用本算法处理右分区（注意要调整k的值，减去左分区的元素数量和M本身）。

补充个关键细节：这个算法能保证线性复杂度的核心原因是，M作为中位数的中位数，至少会有$\frac{3n}{10}$个元素比它小，也至少有$\frac{3n}{10}$个元素比它大，所以每次递归处理的子问题规模最多是$\frac{7n}{10}$，结合递归式$T(n) \leq T(n/5) + T(7n/10) + O(n)$，可以用代入法严格证明$T(n)=O(n)$。

内容的提问来源于stack exchange，提问作者letotyrazdeta