学步园

在一个数组中同时找最大和最小值：时间复杂度O(1.5n)

void find_min_max(int a[],int n,int b[])
{
    int max,min;
    if(n%2==1)//n是奇数的情况
    {
        max=min=0;
        for(int i=1;i!=n;i+=2)//成对比较
        {
            if(a[i]<a[i+1])
            {
                if(a[i]<a[min])
                    min=i;
                if(a[i+1]>a[max])
                    max=i+1;
            }
            else
            {
                if(a[i]>a[max])
                    max=i;
                if(a[i+1]<a[min])
                    min=i+1;
            }
        }
    }
    if(n%2==0)//n是偶数的情况
    {
        if(a[0]<a[1])
        {
            min=0;
            max=1;
        }
        else
        {
            min=1;
            max=0;
        }
        for(int i=2;i!=n;i+=2)
        {
            if(a[i]<a[i+1])
            {
                if(a[i]<a[min])
                    min=i;
                if(a[i+1]>a[max])
                    max=i+1;
            }
            else
            {
                if(a[i]>a[max])
                    max=i;
                if(a[i+1]<a[min])
                    min=i+1;
            }
        }
    }
    b[0]=a[min];
    b[1]=a[max];
}

以期望线性时间做选择：时间复杂度，最坏O(n^2)，平均O(n)

int partition(int a[],int p,int r)
{
    int i,j,x,k;
    x=a[r];
    i=p-1;
    for(j=p;j<=r-1;++j)
    {
        if(a[j]<=x)
        {
            ++i;
            k=a[i];
            a[i]=a[j];
            a[j]=k;
        }
    }
    k=a[++i];
    a[i]=a[r];
    a[r]=k;
    return i;
}
int rand_partition(int a[],int p,int r)
{
    int i=rand()%(r-p+1)+p;
    int k=a[i];
    a[i]=a[r];
    a[r]=k;
    return partition(a,p,r);
}
int randomized_select(int a[],int p,int r,int i)//返回第i小的元素
{
    if(p==r)
        return a[p];
    int q=rand_partition(a,p,r);
    int k=q-p+1;
    if(k==i)
        return a[q];
    else if(k>i)
        return randomized_select(a,p,q-1,i);
    else
        return randomized_select(a,q+1,r,i-k);
}

最坏情况线性时间的选择：时间复杂度最坏O(n)

void insertion_sort(int a[],int n)//插入排序
{
    for(int i=1;i<n;++i)
    {
        int temp=a[i];
        int j=i-1;
        while(j>=0 && a[j]>temp)
        {
            a[j+1]=a[j];
            --j;
        }
        a[j+1]=temp;
    }
}

int find_mid(int a[],int n)//寻找中位数
{
    insertion_sort(a,n);
        return a[(n-1)/2];
}

int Select(int a[],int p,int r,int i)//选择第i小的元素
{
    int x,j;
    int m=(r-p+1)/5;//将输入数组划分为m组，每组5个元素
    int *b=new int[m+1];
    for(j=0;j<m;++j)//寻找每一组的中位数
        b[j]=find_mid(a+p+5*j,5);
    int c=(r-p+1)%5;
    if(c!=0)
    {
        b[m]=find_mid(a+p+5*m,c);//如果还有剩余的不超过5个元素，也对其求中位数
        x=find_mid(b,m+1);//求这些中位数的中位数
    }
    else
        x=find_mid(b,m);
    for(j=0;a[j]!=x;++j);
    a[j]=a[r];
    a[r]=x;
    int q=partition(a,p,r);//按x对数组进行划分
    int k=q-p+1;
    if (k==i)
        return x;
    else if(k>i)
        return Select(a,p,q-1,i);
    else
        return Select(a,q+1,r,i-k);
}

9.3-6:对一个含有n个元素的集合，所谓k分位数(the kth quantile),就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能列出某一集合的k分位数的O(nlgk)时间的算法

void list_quantiles(int a[],int p,int r,int k,int b[])
{
    int j;
    if((r-p+1-k+1)%k!=0)
        cerr<<"不能等分成k个集合"<<endl;
    int blocksize=(r-p+1-k+1)/k;//区块大小
    int q=k/2*(blocksize+1);//先找出第k/2个分割点
    int base=p/(blocksize+1);//前面已经有分割点
    if((r-p)>blocksize)
    {
        b[base+k/2-1]=Select(a,p,r,q);//注意减1，得到第q大的元素存入b中
        for(j=p;a[j]!=b[base+k/2-1];++j);
        int temp=a[j];
        a[j]=a[r];
        a[r]=temp;
        int m=partition(a,p,r);//利用上面得到的元素分割，然后递归
        list_quantiles(a,p,m-1,k/2,b);
        list_quantiles(a,m+1,r,k-k/2,b);
    }
}