求第k大

2019-11-08 20:22:51

字体：大中小

来源：转载

供稿：网友

一个数组中求第k大的数。 4 1 1 3 9 2 求第4大的数。时间复杂度

//4 1 1 3 9 2#include<iostream>#include<cstdio>using namespace std;int a[1001];int n,k;void qst(int l,int r){ if(l>r) return; int tmp=a[l],i=l+1,j=l+1;//a[1] a[2] a[3] a[4] while(i<=r) { if(a[i]>tmp) i++; else swap(a[i],a[j]),i++,j++;//<=交换 } j--; swap(a[l],a[j]); if(j==k) cout<<a[k]<<endl; qst(l,j-1); qst(j+1,r); }int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n);// for(int i=1;i<=n;i++)// cout<<a[i]<<" ";}

双路快排，一直觉得这个比较难写

#include<iostream>#include<cstdio>using namespace std;int n,a[1001];void qst(int l,int r){ if(l>r) return; int tmp=a[l]; int i=l+1,j=r; while(1) { while(i<=r && a[i]<=tmp) i++; while(j>=l+1 && a[j]>=tmp) j--; if(i>j) break; swap(a[i],a[j]); i++; j--; } swap(a[l],a[j]); qst(l,j-1); qst(j+1,r);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" ";}

三路快排，值得一学的是它的边界处理

#include<iostream>#include<cstdio>using namespace std;int n,a[1001];void qst(int l,int r){ if(l>r) return; int tmp=a[l]; int lt=l;//[l+1,lt]< 空 int gt=r+1;//[gt,r]>v 空 int i=l+1;//[lt+1,i)==v 空 while(i<gt) { if(a[i]<tmp){ swap(a[i],a[lt+1]),lt++,i++; } else if(a[i]>tmp) { swap(a[i],a[gt-1]),gt--; } else{ i++; } } swap(a[l],a[lt]); qst(l,lt-1); qst(gt,r);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" ";}

上一篇：Anaconda的安装和基本使用

下一篇：Mybatis自动生成dao,mapping,model文件