Robert W. Floyd

1 Floyd-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
{
    /// <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];}}
}