【随机化算法】舍伍德(Sherwood)算法和线性时间选择问题

1、舍伍德(Sherwood)算法

     设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。

     2、线性时间选择算法

     1)随机划分选择基准

     对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要O(n^2)计算时间。舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。非递归的舍伍德型选择算法如下：

//随机化算法 线性时间选择 随机划分选择基准
#include "RandomNumber.h"
#include <iostream>
using namespace std;

template<class Type>
Type select(Type a[],int l,int r,int k);

template<class Type>
Type select(Type a[],int n,int k);

template <class Type>
inline void Swap(Type &a,Type &b);

int main()
{
    int a[] = {5,7,3,4,8,6,9,1,2};
    cout<<"原数组为："<<endl;
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<"所给数组第7小元素为："<<select(a,9,7)<<endl;
    return 0;
}

//计算a[0:n-1]中第k小元素
//假设a[n]是一个键值无穷大的元素
template<class Type>
Type select(Type a[],int n,int k)
{
    if(k<1 || k>n)
    {
        cout<<"请输入正确的k!"<<endl;
        return 0;
    }
    return select(a,0,n-1,k);
}

//计算a[l:r]中第k小元素
template<class Type>
Type select(Type a[],int l,int r,int k)
{
    static RandomNumber rnd;
    while(true)
    {
        if(l>=r)
        {
            return a[l];
        }

        int i = l,
            j = l + rnd.Random(r-l+1);//随机选择划分基准

        Swap(a[i],a[j]);

        j = r+1;
        Type pivot = a[l];

        //以划分基准为轴做元素交换
        while(true)
        {
            while(a[++i]<pivot);
            while(a[--j]>pivot);
            if(i>=j)
            {
                break;
            }
            Swap(a[i],a[j]);
        }

        if(j-l+1 == k)//第k小
        {
            return pivot;
        }

        //a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大
        a[l] = a[j];
        a[j] = pivot;

        //对子数组重复划分过程
        if(j-l+1<k)
        {
            k = k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1
            l = j + 1;
        }
        else
        {
            r = j - 1;
        }
    }
}

template <class Type>
inline void Swap(Type &a,Type &b)
{
    Type temp = a;
    a = b;
    b = temp;
}

程序运行结果如图：

2)随机洗牌预处理

      有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。例如，对于确定性选择算法，可以用下面的洗牌算法shuffle将数组a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。

//随机化算法 线性时间选择 输入预处理，洗牌

#include "RandomNumber.h"
#include <iostream>
using namespace std;

template<class Type>
Type select(Type a[],int l,int r,int k);

template<class Type>
Type select(Type a[],int n,int k);

template<class Type>
void Shuffle(Type a[],int n);

template <class Type>
inline void Swap(Type &a,Type &b);

int main()
{
    int a[] = {5,7,3,4,8,6,9,1,2};
    cout<<"原数组为："<<endl;
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    Shuffle(a,9);//洗牌
    cout<<"洗牌后数组为："<<endl;
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<"所给数组第7小元素为："<<select(a,9,7)<<endl;
    return 0;
}

//计算a[0:n-1]中第k小元素
//假设a[n]是一个键值无穷大的元素
template<class Type>
Type select(Type a[],int n,int k)
{
    if(k<1 || k>n)
    {
        cout<<"请输入正确的k!"<<endl;
        return 0;
    }
    return select(a,0,n-1,k);
}

//计算a[l:r]中第k小元素
template<class Type>
Type select(Type a[],int l,int r,int k)
{
    while(true)
    {
        if(l>=r)
        {
            return a[l];
        }
        int i = l;
        int j = r+1;
        Type pivot = a[l];

        //以划分基准为轴做元素交换
        while(true)
        {
            while(a[++i]<pivot);
            while(a[--j]>pivot);
            if(i>=j)
            {
                break;
            }
            Swap(a[i],a[j]);
        }

        if(j-l+1 == k)//第k小
        {
            return pivot;
        }

        //a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大
        a[l] = a[j];
        a[j] = pivot;

        //对子数组重复划分过程
        if(j-l+1<k)
        {
            k = k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1
            l = j + 1;
        }
        else
        {
            r = j - 1;
        }
    }
}

template <class Type>
inline void Swap(Type &a,Type &b)
{
    Type temp = a;
    a = b;
    b = temp;
}

//随机洗牌算法
template<class Type>
void Shuffle(Type a[],int n)
{
    static RandomNumber rnd;
    for(int i=0; i<n; i++)
    {
        int j = rnd.Random(n-i)+i;
        Swap(a[i],a[j]);
    }
}