舍伍德算法改进快速排序 (二)

法二：

[cpp] #include
#include
#include
#include
#include
#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] 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 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"< for(int i=1;i<=n;++i) cin>>a[i];
cout< }return 0;
}

#include
#include
#include
#include
#include
#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] 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 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"< for(int i=1;i<=n;++i) cin>>a[i];
cout< }return 0;
}

法三：

[cpp] #include
#include
#include
#include
#include
#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] {
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"< for(int i=1;i<=n;++i) cin>>a[i];
cout< }return 0;
}

#include
#include
#include
#include
#include
#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] {
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(