我想在未排序的列表中找到近似中值，我知道两种算法
算法1-快速选择
算法2-中值
我不能在我的项目中使用快速选择，因为在最坏的情况下它需要O(n^2)。我听说过中位数，但我的同事认为它需要O(n)和一些常数因子。因此，它的时间复杂度是Cn，常数因子与快速选择相比很大。我想知道什么是与中位数相关的常数因子？为什么中位数不使用9元素的伪中位数
或者他们有其他算法来寻找线性时间O(n)中的近似中值吗？
虽然我不会很快放弃quickselect，因为如果枢轴选择得当，它最坏的性能是不可能的。。。
也许介绍：
Introselect("内省选择"的缩写)是一种混合了快速选择和中值的选择算法，具有快速平均性能和最佳最坏情况性能。
Introselect的工作原理是乐观地从快速选择开始，只有在重复次数太多而没有取得足够进展的情况下才切换到最差时间线性算法。切换策略是算法的主要技术内容。仅仅将递归限制为恒定深度是不够的，因为这会使算法在所有足够大的列表上切换。Musser讨论了几个简单的方法：
- 跟踪到目前为止处理的子分区的大小列表。如果在任何一点上，在没有将列表大小减半的情况下进行了k次递归调用，对于一些较小的正k，则切换到最坏情况下的线性算法
- 求和到目前为止生成的所有分区的大小。如果这超过了列表大小乘以某个小的正常数k，则切换到最坏情况下的线性算法。这个和很容易在单个标量变量中跟踪
这两种方法都将递归深度限制为kålog nå=O(log n)，并将总运行时间限制为O(n)。