算法实验（一）递归与分治

求运行时间

快速排序
#include
using namespace std;
const int maxn=1e6+7;
int a[maxn],n; 
int Partition(int *a,int p,int r){
    int i=p,j=r+1;
    int x=a[p];
    while(1){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];a[j]=x;
    return j;
}                    
void QuickSort(int *a,int p,int r){
    if(p<r){
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}                                                                                      
int main(){
    cin>>n;
    for(int i=0;i>a[i];
    QuickSort(a,0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

随机化

#include
using namespace std;
const int maxn=1e6+7;
int a[maxn],n; 
int Partition(int *a,int p,int r){
    int i=p,j=r+1;
    int x=a[p];
    while(1){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];a[j]=x;
    return j;
}     
int Random(int l,int r){
    r++;
    return (rand()*rand()+rand())%(r-l)+l;
}
int RandomizedPartition(int *a,int p,int r){
    int i=Random(p,r);
    swap(a[i],a[p]);
    return Partition(a,p,r);
}                    
void RandomizedQuickSort(int *a,int p,int r){
    if(p<r){
        int q=RandomizedPartition(a,p,r);
        RandomizedQuickSort(a,p,q-1);
        RandomizedQuickSort(a,q+1,r);
    }
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
int main(){
    srand(time(0));
    cin>>n;
    for(int i=0;i>a[i];
    RandomizedQuickSort(a,0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

随机求第k小

#include
using namespace std;
const int maxn=1e6+7;
int a[maxn],n,k; 
int Partition(int *a,int p,int r){
    int i=p,j=r+1;
    int x=a[p];
    while(1){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];a[j]=x;
    return j;
}     
int Random(int l,int r){
    r++;
    return (rand()*rand()+rand())%(r-l)+l;
}
int RandomizedPartition(int *a,int p,int r){
    int i=Random(p,r);
    swap(a[i],a[p]);
    return Partition(a,p,r);
}                    
int RandomizedSelect(int *a,int p,int r,int k){
    if(p==r) return a[p];
    int i=RandomizedPartition(a,p,r),j=i-p+1;
    if(k<=j) return RandomizedSelect(a,p,i,k);
    else return RandomizedSelect(a,i+1,r,k-j);
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
int main(){
    srand(time(0));
    cin>>n>>k;
    for(int i=0;i>a[i];
    cout<<RandomizedSelect(a,0,n-1,k)<<endl;
    return 0;
}

线性时间求第k小

#include
using namespace std;
const int maxn=1e6+7;
int a[maxn],n,k; 
int Partition(int *a, int p, int n, int beginval)
{
    int temp, beginpos;
    for(int i = 0; p <= n - p + 1; ++i)
        if(a[p + i] == beginval)
        {
          beginpos = p + i;
          break;
        }
    temp = a[p];
    a[p] = a[beginpos];
    a[beginpos] = temp;
    temp = a[p];
    while(p < n)
    {
        while(a[n] >= temp && p < n) --n;
        a[p] = a[n];
        while(a[p] <= temp && p < n) ++p;
        a[n] = a[p];
    }
    a[p] = temp;
    return p;
}
int Select(int *a,int l,int r,int k){
    if(r-l<75){
        sort(a+l,a+r);
        return a[l+k-1];
    }
    int m=(r-l+1)/5;
    if(5*m!=r-l+1) m++;
    int i;
    for(i=0;i<m-1;i++){
        sort(a+l+i*5,a+l+i*5+4);
        swap(a[l+i],a[l+i*5+2]);
    }
    sort(a+l+i*5,a+n);
    int midval=Select(a,l,l+m,m/2);
    int midpos=Partition(a,l,r,midval);
    int tmp=midpos-l+1;
    if(k<=tmp)
        return Select(a,l,midpos,k);
    else return Select(a,midpos+1,r,k-tmp);
}
int main(){
    cin>>n>>k;
    for(int i=0;i>a[i];
    cout<<Select(a,0,n,k);
    return 0;
}