捨伍德算法改進快速排序

由於快速排序具有不穩定性，最好的時間復雜度為o（nlogn），而最壞可達到o(n^2),為了降低最壞情況出現的概率，可以用捨伍德算法對其進行改進～

[cpp] 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; 
} 

#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小數：

[cpp] #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];
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;
}

法二：

[cpp]  #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],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;
}

法三：

[cpp]  #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; 
} 

#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;
}