学步园

由于快速排序具有不稳定性，最好的时间复杂度为o（nlogn），而最坏可达到o(n^2),为了降低最坏情况出现的概率，可以用舍伍德算法对其进行改进～

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<cstdio>
#include<algorithm>
#define N 1000
using namespace std;
int a[N];
int Partion(int l,int r)
{
    int key=a[l];
    int i=l,j=r+1;
    while(1)
    {

        while(a[++i]<key&&i<=r);
        while(a[--j]>key&&j>=l);
        if(i>=j) break;
        if(a[i]!=a[j]) swap(a[i],a[j]);
    }
     if((j!=l)&&(a[l]!=a[j])) swap(a[l],a[j]);
     return j;
}
int Randpartion(int l,int r)
{
    srand(time(NULL));
    int k=rand()%(r-l+1)+l;
    swap(a[k],a[l]);
    k=Partion(l,r);
    return k;
}
void Quick_sort(int l,int r)
{
    if(l<r)
    {

       int k=Randpartion(l,r);
       Quick_sort(l,k-1);
       Quick_sort(k+1,r);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        Quick_sort(1,n);
        for(int i=1;i<=n;++i) cout<<a[i]<<" ";
        cout<<endl;
    }return 0;
}

运用快速排序求第k大数和第k小数：

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<cstdio>
#include<algorithm>
#define N 1000
using namespace std;
int a[N],b[N];
int Partion(int a[],int l,int r)
{
    int key=a[l];
    int i=l,j=r+1;
    while(1)
    {

        while(a[++i]<key&&i<=r);
        while(a[--j]>key&&j>=l);
        if(i>=j) break;
        if(a[i]!=a[j]) swap(a[i],a[j]);
    }
     if((j!=l)&&(a[l]!=a[j])) swap(a[l],a[j]);
     return j;
}
int Randpartion(int a[],int l,int r)
{
    srand(time(NULL));
    int k=rand()%(r-l+1)+l;
    swap(a[k],a[l]);
    int ans=Partion(a,l,r);
    return ans;
}
int Quick_sort(int a[],int l,int r,int k)
{
       int p=Randpartion(a,l,r);
       if(p==k) return a[k];
       else if(k<p) return Quick_sort(a,l,p-1,k);
       else  {
                int j=0;
                for(int i=p+1;i<=r;++i) b[++j]=a[i];
                return Quick_sort(b,1,j,k-p);
             }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        if(k<1||k>n) {cout<<"-1"<<endl;continue;}
        for(int i=1;i<=n;++i) cin>>a[i];
        cout<<Quick_sort(a,1,n,n+1-k)<<endl;
    }return 0;
}

法二：

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<cstdio>
#include<algorithm>
#define N 1000
using namespace std;
int a[N],b[N],tot;
int Partion(int l,int r)
{
    int key=a[l];
    int i=l,j=r+1;
    while(1)
    {

        while(a[++i]<key&&i<=r);
        while(a[--j]>key&&j>=l);
        if(i>=j) break;
        if(a[i]!=a[j]) swap(a[i],a[j]);
    }
     if((j!=l)&&(a[l]!=a[j])) swap(a[l],a[j]);
     tot=0;
     for(i=l;i<=r;++i)
     {
        tot++;
        if(i==j) break;
     }
     return j;
}
int Randpartion(int l,int r)
{
    srand(time(NULL));
    int k=rand()%(r-l+1)+l;
    swap(a[k],a[l]);
    int ans=Partion(l,r);
    return ans;
}
int Quick_sort(int l,int r,int k)
{
       int p=Randpartion(l,r);
       if(tot==k) return a[p];
       else if(k<tot) return Quick_sort(l,p-1,k);
       else  return Quick_sort(p+1,r,k-tot);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        if(k<1||k>n) {cout<<"-1"<<endl;continue;}
        for(int i=1;i<=n;++i) cin>>a[i];
        cout<<Quick_sort(1,n,n+1-k)<<endl;
    }return 0;
}

法三：

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<cstdio>
#include<algorithm>
#define N 1000
using namespace std;
int a[N],b[N];
int Quick_sort(int l,int r,int k)
{
    srand(time(NULL));
    int p=rand()%(r-l+1)+l;
    swap(a[p],a[l]);
    int i=l;
    int tot=1;
    for(int j=i+1;j<=r;++j)//把大于基准点的值都放到它的左边
     if(a[l]<a[j])
    {
        tot++;
        swap(a[++i],a[j]);
    }
    swap(a[l],a[i]);
    if(tot==k) return a[i];
    else if(tot>k) return Quick_sort(l,i-1,k);
    else    return Quick_sort(i+1,r,k-tot);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        if(k<1||k>n) {cout<<"-1"<<endl;continue;}
        for(int i=1;i<=n;++i) cin>>a[i];
        cout<<Quick_sort(1,n,k)<<endl;
    }return 0;
}