Robert W. Floyd
1 Floyd-Rivest 算法
Floyd-Rivest 算法是一种选择算法，用于在不同元素的数组中找到第k个最小元素。它类似于快速选择算法，但在实际运行中有更好的运行时间。 和 QuickSelect 一样，该算法基于分区的思想工作。对数组进行分区后，分区元素会在正确的排序位置结束。如果数组有所有不同的元素，检索第(k+1) 个个最小元素与排序后检索第(k+1) 个个元素相同。因为完全排序是昂贵的(需要 O(N log N) 来计算)，所以 Floyd-Rivest 算法利用分区在 O(N) 时间内完成相同的工作。
算法流程:
- 如果所考虑的数组 S 的大小足够小，则直接应用快速选择算法来获得第 K 个最小元素。这个大小是算法的任意常数，作者选择它作为 600 。
- 否则，使用随机抽样选择 2 个枢轴- newLeftIndex 和 newRightIndex，使得它们具有包含第 K 个最大元素的最高概率。然后，递归调用该函数，数组的左右边界现在设置为 newLeftIndex 和 newRightIndex。
- 像快速选择一样，在划分子阵列后，需要设置左右边界，使它们包含 K 最大的元素。 围绕 K 分割数组后，第 K 个元素处于其正确的排序位置。因此，左右边界以这样一种方式设置，即所考虑的子阵列包含数组[k]。
2 源程序
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
/// <summary>
/// 弗洛伊德-瑞文斯特算法
/// Floyd Rivest Algorithm
/// </summary>
public static partial class Algorithm_Gallery
{
private static int Sign(double x)
{
return (x < 0) ? -1 : (x > 0) ? 1 : 0;
}
private static void Swap(ref int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int Floyd_Rivest(int[] arr, int left, int right, int k)
{
int i;
while (right > left)
{
if ((right - left) > 600)
{
int n = right - left + 1;
i = k - left + 1;
double z = Math.Log(n);
double s = 0.5 * Math.Exp(2 * z / 3);
double sd = 0.5 * Math.Sqrt(z * s * (n - s) / n) * Sign(i - n / 2);
int newLeft = Math.Max(left, (int)(k - i * s / n + sd));
int newRight = Math.Min(right, (int)(k + (n - i) * s / n + sd));
Floyd_Rivest(arr, newLeft, newRight, k);
}
int t = arr[k];
i = left;
int j = right;
Swap(ref arr, left, k);
if (arr[right] > t)
{
Swap(ref arr, left, right);
}
while (i < j)
{
Swap(ref arr, i, j);
i++;
j--;
while (arr[i] < t)
{
i++;
}
while (arr[j] > t)
{
j--;
}
}
if (arr[left] == t)
{
Swap(ref arr, left, j);
}
else
{
j++;
Swap(ref arr, right, j);
}
if (j <= k)
{
left = j + 1;
}
if (k <= j)
{
right = j - 1;
}
}
return arr[k];
}
}
}
POWER BY 315SOFT.COM
3 源代码
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
/// <summary>
/// 弗洛伊德-瑞文斯特算法
/// Floyd Rivest Algorithm
/// </summary>
public static partial class Algorithm_Gallery
{
private static int Sign(double x)
{
return (x < 0) ? -1 : (x > 0) ? 1 : 0;
}
private static void Swap(ref int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int Floyd_Rivest(int[] arr, int left, int right, int k)
{
int i;
while (right > left)
{
if ((right - left) > 600)
{
int n = right - left + 1;
i = k - left + 1;
double z = Math.Log(n);
double s = 0.5 * Math.Exp(2 * z / 3);
double sd = 0.5 * Math.Sqrt(z * s * (n - s) / n) * Sign(i - n / 2);
int newLeft = Math.Max(left, (int)(k - i * s / n + sd));
int newRight = Math.Min(right, (int)(k + (n - i) * s / n + sd));
Floyd_Rivest(arr, newLeft, newRight, k);
}
int t = arr[k];
i = left;
int j = right;
Swap(ref arr, left, k);
if (arr[right] > t)
{
Swap(ref arr, left, right);
}
while (i < j)
{
Swap(ref arr, i, j);
i++;
j--;
while (arr[i] < t)
{
i++;
}
while (arr[j] > t)
{
j--;
}
}
if (arr[left] == t)
{
Swap(ref arr, left, j);
}
else
{
j++;
Swap(ref arr, right, j);
}
if (j <= k)
{
left = j + 1;
}
if (k <= j)
{
right = j - 1;
}
}
return arr[k];
}
}
}
