Robert W. Floyd

1Floyd-Rivest 算法

Floyd-Rivest 算法是一种选择算法，用于在不同元素的数组中找到第k个最小元素。它类似于快速选择算法，但在实际运行中有更好的运行时间。 和 QuickSelect 一样，该算法基于分区的思想工作。对数组进行分区后，分区元素会在正确的排序位置结束。如果数组有所有不同的元素，检索第(k+1) 个个最小元素与排序后检索第(k+1) 个个元素相同。因为完全排序是昂贵的(需要 O(N log N) 来计算)，所以 Floyd-Rivest 算法利用分区在 O(N) 时间内完成相同的工作。

算法流程:

  1. 如果所考虑的数组 S 的大小足够小，则直接应用快速选择算法来获得第 K 个最小元素。这个大小是算法的任意常数，作者选择它作为 600 。
  2. 否则，使用随机抽样选择 2 个枢轴- newLeftIndex 和 newRightIndex，使得它们具有包含第 K 个最大元素的最高概率。然后，递归调用该函数，数组的左右边界现在设置为 newLeftIndex 和 newRightIndex。
  3. 像快速选择一样，在划分子阵列后，需要设置左右边界，使它们包含 K 最大的元素。 围绕 K 分割数组后，第 K 个元素处于其正确的排序位置。因此，左右边界以这样一种方式设置，即所考虑的子阵列包含数组[k]。

2 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
///

/// 弗洛伊德-瑞文斯特算法
/// Floyd Rivest Algorithm
///

public static partial class Algorithm_Gallery
{
private static int Sign(double x)
{
return (x

3 源代码

using System;using System.Collections;using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm{/// /// 弗洛伊德-瑞文斯特算法/// Floyd Rivest Algorithm/// public static partial class Algorithm_Gallery{private static int Sign(double x){return (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){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];}}}