2.5.23 #
解答 #
这里我们使用 Floyd-Rivest 算法进行优化，大致思想是：
我们期望第 $k$ 大的元素位于 a[k] 附近，因此优先对 a[k] 附近的区域进行选择。
每次切分时枢轴都选择 a[k]，先递归对样本区域选择，再对整个数组进行选择。
运行示意图：
测试结果：
代码 #
// Floyd–Rivest 方法优化，令 a[k] 变成第 k 小的元素。
static T SelectInternal<T>(T[] a, int lo, int hi, int k) where T : IComparable<T>
{
if (k < 0 || k > a.Length)
{
throw new IndexOutOfRangeException("SelectInternal elements out of bounds");
}
while (hi > lo)
{
if (hi - lo > 600)
{
var n = hi - lo + 1;
var i = k - lo + 1;
var z = (int)Math.Log(n);
var s = (int)(Math.Exp(2 * z / 3) / 2);
var sd = (int)Math.Sqrt(z * s * (n - s) / n) * Math.Sign(i - n / 2) / 2;
var newLo = Math.Max(lo, k - i * s / n + sd);
var newHi = Math.Min(hi, k + (n - i) * s / n + sd);
SelectInternal(a, newLo, newHi, k);
}
Exch(a, lo, k);
var j = Partition(a, lo, hi);
if (j > k)
{
hi = j - 1;
}
else if (j < k)
{
lo = j + 1;
}
else
{
return a[j];
}
}
return a[lo];
}